Talks and Poster Presentations (with Proceedings-Entry):
T. Hamm:
"Finding Linear Arrangements of Hypergraphs with Bounded Cutwidth in Linear Time";
Talk: International Symposium on Parameterized and Exact Computation (IPEC),
München;
2019-09-11
- 2019-09-13; in: "14th International Symposium on Parameterized and Exact Computation",
LIPIcs,
148
(2019),
ISBN: 978-3-95977-129-0;
1
- 14.
English abstract:
Cutwidth is a fundamental graph layout parameter. It generalises to hypergraphs in a natural way
and has been studied in a wide range of contexts. For graphs it is known that for a fixed constant k
there is a linear time algorithm that for any given G, decides whether G has cutwidth at most k
and, in the case of a positive answer, outputs a corresponding linear arrangement. We show that
such an algorithm also exists for hypergraphs.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.IPEC.2019.0
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_284992.pdf
Created from the Publication Database of the Vienna University of Technology.