Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
R. Pichler, St. Rümmele, S. Woltran:
"Multicut Algorithms via Tree Decompositions";
Vortrag: 7#{th}^Int. Conference on Algorithms and Complexity - CIAC 2010,
Rome, Italy;
26.05.2010
- 28.05.2010; in: "Algorithms and Complexity",
T. Calamoneri, J. Diaz (Hrg.);
LNCS, Springer,
6078
(2010),
ISBN: 978-3-642-13072-4;
S. 167
- 179.
Kurzfassung englisch:
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.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-13073-1_16
Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_186197.pdf
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung
Projektleitung Stefan Woltran:
Neue Methoden für Analyse, Vergleich und Lösung von Argumentationsproblemen
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.