[Back]

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

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.

Tree decompositions Dynamic programming Software library

http://dx.doi.org/10.1017/S1471068417000382

Project Head Nysret Musliu:
Künstliche Intelligenz in der Personalplanung

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

Project Head Stefan Woltran:
START