Talks and Poster Presentations (with Proceedings-Entry):

M. Lackner, R. Pichler, St. Rümmele, S. Woltran:
"Multicut on Graphs of Bounded Clique-width";
Talk: Annual International Conference on Combinatiorial Optimization and Applications (COCOA), Banff, Canada; 2012-08-05 - 2012-08-09; in: "Lecture Notes of Computer Science", G. Lin (ed.); Springer, 7402 (2012), ISBN: 978-3-642-31769-9; 115 - 126.

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

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Related Projects:
Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung

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