[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

M. Abseher, N. Musliu, S. Woltran:
"htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond";
Vortrag: 14th International Conference on Integration of AI and OR Teniques (CPAIOR) 2017, Padua, Italien; 05.06.2017 - 08.06.2017; in: "CPAIOR 2017", Lecture Notes in Computer Science / Springer, 10335 (2017), ISBN: 978-3-319-59775-1; S. 376 - 386.



Kurzfassung englisch:
Decompositions of graphs play a central role in the field of parameterized complexity and are the basis for many fixed-parameter tractable algorithms for problems that are NP-hard in general. Tree decompositions are the most prominent concept in this context and several tools for computing tree decompositions recently competed in the 1st Parameterized Algorithms and Computational Experiments Challenge. However, in practice the quality of a tree decomposition cannot be judged without taking concrete algorithms that make use of tree decompositions into account. In fact, practical experience has shown that generating decompositions of small width is not the only crucial ingredient towards efficiency. To this end, we present htd, a free and open-source software library, which includes efficient implementations of several heuristic approaches for tree decomposition and offers various features for normalization and customization of decompositions. The aim of this article is to present the specifics of htd together with an experimental evaluation underlining the effectiveness and efficiency of the implementation.

Schlagworte:
Tree decompositions Dynamic programming Software library


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1017/S1471068417000382



Zugeordnete Projekte:
Projektleitung Nysret Musliu:
Künstliche Intelligenz in der Personalplanung

Projektleitung Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Projektleitung Stefan Woltran:
START


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.