Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
T. Hamm:
"Finding Linear Arrangements of Hypergraphs with Bounded Cutwidth in Linear Time";
Vortrag: International Symposium on Parameterized and Exact Computation (IPEC),
München;
11.09.2019
- 13.09.2019; in: "14th International Symposium on Parameterized and Exact Computation",
LIPIcs,
148
(2019),
ISBN: 978-3-95977-129-0;
S. 1
- 14.
Kurzfassung englisch:
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.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.IPEC.2019.0
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_284992.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.