Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
G. Gottlob, M. Lanzinger, R. Pichler, I. Razgon:
"Fractional Covers of Hypergraphs with BoundedMulti-Intersection";
Vortrag: MFCS 2020 - International Symposium on Mathematical Foundations of Computer Science,
Prag;
24.08.2020
- 28.08.2020; in: "45th International Symposium on Mathematical Foundations of Computer Science August 24-28, 2020, Prague (Czech Republic)",
(2020),
S. 1
- 14.
Kurzfassung englisch:
Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractionalanalogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paperis on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previousconditions under which the size of the support of fractional edge covers is bounded independently ofthe size of the hypergraph itself. This allows us to extend previous tractability results for checkingif the fractional hypertree width of a given hypergraph is≤kfor some constantk. We also showhow our results translate to fractional vertex covers.
Schlagworte:
Fractional graph theory, fractional edge cover, fractional hypertree width,bounded multi-intersection, fractional cover, fractional vertex cover
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.41
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.