Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Lackner, R. Pichler, St. Rümmele, S. Woltran:
"Multicut on Graphs of Bounded Clique-width";
Vortrag: Annual International Conference on Combinatiorial Optimization and Applications (COCOA),
Banff, Canada;
05.08.2012
- 09.08.2012; in: "Lecture Notes of Computer Science",
G. Lin (Hrg.);
Springer,
7402
(2012),
ISBN: 978-3-642-31769-9;
S. 115
- 126.
Kurzfassung englisch:
Several variants of Multicut problems arise in applications like circuit and network design. In general, these problems are NP-complete. The goal of our work is to investigate the potential of clique-width for identifying tractable fragments of Multicut. We show for several parameterizations involving clique-width whether they lead to tractability or not. Since bounded tree-width implies bounded clique-width, our tractability results extend previous results via tree-width, in particular to dense graphs.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-31770-5_11
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.