Jdrasil: A Modular Library for Computing Tree Decompositions

Max Bannach, Sebastian Berndt, Thorsten Ehlers


While the theoretical aspects concerning the computation of tree width - one of the most important graph parameters - are well understood, it is not clear how it can be computed practically. We present the open source Java library Jdrasil that implements several different state of the art algorithms for this task. By experimentally comparing these algorithms, we show that the default choices made in Jdrasil lead to an competitive implementation (it took the third place in the first PACE challenge) while also being easy to use and easy to extend.

Original languageEnglish
Title of host publication16th International Symposium on Experimental Algorithms (SEA 2017)
EditorsCostas S. Iliopoulos, Solon P. Pissis , Simon J. Puglisi, Rajeev Raman
Number of pages21
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date01.08.2017
ISBN (Print)978-3-95977-036-1
Publication statusPublished - 01.08.2017
Event16th International Symposium on Experimental Algorithms (SEA 2017)
- King's College , London, United Kingdom
Duration: 21.06.201723.07.2017


Dive into the research topics of 'Jdrasil: A Modular Library for Computing Tree Decompositions'. Together they form a unique fingerprint.

Cite this