Skip to Content

TU Wien Fakultät für Informatik DBAI Database and Artificial Intelligence Group
Top-level Navigation: Current-level Navigation:

Path: DBAI > Research > Projects > Decodyn > htd

Tools: Print


htd

A small but efficient C++ library for computing
(customized) tree and hypertree decompositions


About

htd is a software library which does not only compute tree decompositions, it also allows to fully customize them via (custom) manipulations, labelings and optimize them based on a user-provided fitness function. The library provides efficient implementations of several well-established techniques for computing tree decompositions (like bucket-elimination based on a vertex elimination ordering of the input graph) and it is optimized for large (hyper)graphs. At the current stage, htd is able to decompose graphs containing millions of vertices and several hundreds of thousands of (hyper)edges efficiently.

For almost each class used in the library, htd provides an interface and a corresponding factory class allowing to directly influence the process of generating decompositions without having to re-invent the wheel at any place. That is, if one for instance develops a new heuristic for vertex elimination orderings there is absolutely no need to change anything in the remainder of the library in order to test its influence on the quality of bucket-elimination. (In fact, one does not even need to re-compile htd for such a modification as long as all interfaces are implemented properly by the new algorithm and as long as the algorithm is made available to htd via the corresponding factory class.)

A small example application demonstrating the usage of htd, the source code of the framework as well as further documentation are provided at Github .

Related Projects

Currently, htd is used successfully in the following projects:

Awards

Downloads

Releases:

The latest releases (including source code) are available at: Github .

Evaluation Instances:

References

2017

  1. Michael Abseher Tailored Tree Decompositions for Efficient Problem Solving Ph.D. Thesis, TU Wien, 2017.
    Supervision: Stefan Woltran and Nysret Musliu
    [ Abstract | BibTeX ]
  2. Michael Abseher, Nysret Musliu and Stefan Woltran htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond In Proceedings of the 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2017), 2017.
    To appear.
    [ Abstract | BibTeX ]

2016

  1. Michael Abseher, Nysret Musliu and Stefan Woltran htd - A Free, Open-Source Framework for Tree Decompositions and Beyond Technical Report DBAI-TR-2016-96, DBAI, Fakultät für Informatik an der Technischen Universität Wien, 2016.
    [ Abstract | BibTeX | pdf  ]
Top
Last updated: 2017-06-30 08:33

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Informationssysteme an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. / Disclaimer.