[Back]


Talks and Poster Presentations (with Proceedings-Entry):

G. Gottlob, M. Lanzinger, R. Pichler, I. Razgon:
"Fractional Covers of Hypergraphs with BoundedMulti-Intersection";
Talk: MFCS 2020 - International Symposium on Mathematical Foundations of Computer Science, Prag; 2020-08-24 - 2020-08-28; in: "45th International Symposium on Mathematical Foundations of Computer Science August 24-28, 2020, Prague (Czech Republic)", (2020), 1 - 14.



English abstract:
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.

Keywords:
Fractional graph theory, fractional edge cover, fractional hypertree width,bounded multi-intersection, fractional cover, fractional vertex cover


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.41


Created from the Publication Database of the Vienna University of Technology.