Jdrasil: A Modular Library for Computing Tree Decompositions

Max Bannach; Sebastian Berndt; Thorsten Ehlers

doi:10.4230/LIPIcs.SEA.2017.28

Jdrasil: A Modular Library for Computing Tree Decompositions

Max Bannach, Sebastian Berndt, Thorsten Ehlers

Institute of Theoretical Computer Science

University of Kiel

Abstract

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 language	English
Title of host publication	16th International Symposium on Experimental Algorithms (SEA 2017)
Editors	Costas S. Iliopoulos, Solon P. Pissis , Simon J. Puglisi, Rajeev Raman
Number of pages	21
Volume	75
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date	01.08.2017
ISBN (Print)	978-3-95977-036-1
DOIs	https://doi.org/10.4230/LIPIcs.SEA.2017.28
Publication status	Published - 01.08.2017
Event	16th International Symposium on Experimental Algorithms (SEA 2017) - King's College , London, United Kingdom Duration: 21.06.2017 → 23.07.2017 https://nms.kcl.ac.uk/informatics/events/SEA2017/

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.4230/LIPIcs.SEA.2017.28

http://drops.dagstuhl.de/opus/volltexte/2017/7605/pdf/LIPIcs-SEA-2017-28.pdf

Cite this

Bannach, M., Berndt, S., & Ehlers, T. (2017). Jdrasil: A Modular Library for Computing Tree Decompositions. In C. S. Iliopoulos, S. P. Pissis , S. J. Puglisi, & R. Raman (Eds.), 16th International Symposium on Experimental Algorithms (SEA 2017) (Vol. 75). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 75). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SEA.2017.28

Bannach, Max ; Berndt, Sebastian ; Ehlers, Thorsten. / Jdrasil: A Modular Library for Computing Tree Decompositions. 16th International Symposium on Experimental Algorithms (SEA 2017). editor / Costas S. Iliopoulos ; Solon P. Pissis ; Simon J. Puglisi ; Rajeev Raman. Vol. 75 Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{ac6113cdd7a043019e3436c616dab0bf,

title = "Jdrasil: A Modular Library for Computing Tree Decompositions",

abstract = "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.",

author = "Max Bannach and Sebastian Berndt and Thorsten Ehlers",

year = "2017",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.SEA.2017.28",

language = "English",

isbn = "978-3-95977-036-1",

volume = "75",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Iliopoulos, {Costas S. } and {Pissis }, {Solon P. } and Puglisi, {Simon J. } and Raman, {Rajeev }",

booktitle = "16th International Symposium on Experimental Algorithms (SEA 2017)",

note = "16th International Symposium on Experimental Algorithms (SEA 2017)<br/> ; Conference date: 21-06-2017 Through 23-07-2017",

url = "https://nms.kcl.ac.uk/informatics/events/SEA2017/",

}

Bannach, M, Berndt, S & Ehlers, T 2017, Jdrasil: A Modular Library for Computing Tree Decompositions. in CS Iliopoulos, SP Pissis , SJ Puglisi & R Raman (eds), 16th International Symposium on Experimental Algorithms (SEA 2017). vol. 75, Leibniz International Proceedings in Informatics (LIPIcs), vol. 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 16th International Symposium on Experimental Algorithms (SEA 2017)
, London, United Kingdom, 21.06.17. https://doi.org/10.4230/LIPIcs.SEA.2017.28

Jdrasil: A Modular Library for Computing Tree Decompositions. / Bannach, Max; Berndt, Sebastian; Ehlers, Thorsten.
16th International Symposium on Experimental Algorithms (SEA 2017). ed. / Costas S. Iliopoulos; Solon P. Pissis ; Simon J. Puglisi; Rajeev Raman. Vol. 75 Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 75).

Research output: Chapters in Books/Reports/Conference Proceedings › Conference contribution › peer-review

TY - GEN

T1 - Jdrasil: A Modular Library for Computing Tree Decompositions

AU - Bannach, Max

AU - Berndt, Sebastian

AU - Ehlers, Thorsten

PY - 2017/8/1

Y1 - 2017/8/1

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.SEA.2017.28

DO - 10.4230/LIPIcs.SEA.2017.28

M3 - Conference contribution

SN - 978-3-95977-036-1

VL - 75

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 16th International Symposium on Experimental Algorithms (SEA 2017)

A2 - Iliopoulos, Costas S.

A2 - Pissis , Solon P.

A2 - Puglisi, Simon J.

A2 - Raman, Rajeev

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl, Germany

T2 - 16th International Symposium on Experimental Algorithms (SEA 2017)<br/>

Y2 - 21 June 2017 through 23 July 2017

ER -

Bannach M, Berndt S, Ehlers T. Jdrasil: A Modular Library for Computing Tree Decompositions. In Iliopoulos CS, Pissis SP, Puglisi SJ, Raman R, editors, 16th International Symposium on Experimental Algorithms (SEA 2017). Vol. 75. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2017. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.SEA.2017.28

Jdrasil: A Modular Library for Computing Tree Decompositions

Abstract

UN SDGs

Access to Document

Fingerprint

Cite this