Talks and Poster Presentations (with Proceedings-Entry):
R. Pichler, St. Rümmele, S. Woltran:
"Multicut Algorithms via Tree Decompositions";
Talk: 7#{th}^Int. Conference on Algorithms and Complexity - CIAC 2010,
Rome, Italy;
2010-05-26
- 2010-05-28; in: "Algorithms and Complexity",
T. Calamoneri, J. Diaz (ed.);
LNCS, Springer,
6078
(2010),
ISBN: 978-3-642-13072-4;
167
- 179.
English abstract:
Various forms of multicut problems are of great importance in the area of network design. In general, these problems are intractable. However, several parameters have been identified which lead to fixed-parameter tractability (FPT). Recently, Gottlob and Lee have proposed the treewidth of the structure representing the graph and the set of pairs of terminal vertices as one such parameter. In this work, we show how this theoretical FPT result can be turned into efficient algorithms for optimization, counting, and enumeration problems in this area.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-13073-1_16
Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_186197.pdf
Related Projects:
Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung
Project Head Stefan Woltran:
Neue Methoden für Analyse, Vergleich und Lösung von Argumentationsproblemen
Created from the Publication Database of the Vienna University of Technology.