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

Institut für Theoretische Informatik

Christian-Albrechts Universität zu 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.

Originalsprache	Englisch
Titel	16th International Symposium on Experimental Algorithms (SEA 2017)
Redakteure/-innen	Costas S. Iliopoulos, Solon P. Pissis , Simon J. Puglisi, Rajeev Raman
Seitenumfang	21
Band	75
Erscheinungsort	Dagstuhl, Germany
Herausgeber (Verlag)	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Erscheinungsdatum	01.08.2017
ISBN (Print)	978-3-95977-036-1
DOIs	https://doi.org/10.4230/LIPIcs.SEA.2017.28
Publikationsstatus	Veröffentlicht - 01.08.2017
Veranstaltung	16th International Symposium on Experimental Algorithms (SEA 2017) - King's College , London, Großbritannien / Vereinigtes Königreich Dauer: 21.06.2017 → 23.07.2017 https://nms.kcl.ac.uk/informatics/events/SEA2017/

UN SDGs

Dieser Output leistet einen Beitrag zu folgendem(n) Ziel(en) für nachhaltige Entwicklung

Zugriff auf Dokument

10.4230/LIPIcs.SEA.2017.28

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

Zitieren

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 (Hrsg.), 16th International Symposium on Experimental Algorithms (SEA 2017) (Band 75). (Leibniz International Proceedings in Informatics (LIPIcs); Band 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). Hrsg. / Costas S. Iliopoulos ; Solon P. Pissis ; Simon J. Puglisi ; Rajeev Raman. Band 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 (Hrsg.), 16th International Symposium on Experimental Algorithms (SEA 2017). Bd. 75, Leibniz International Proceedings in Informatics (LIPIcs), Bd. 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 16th International Symposium on Experimental Algorithms (SEA 2017)
, London, Großbritannien / Vereinigtes Königreich, 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). Hrsg. / Costas S. Iliopoulos; Solon P. Pissis ; Simon J. Puglisi; Rajeev Raman. Band 75 Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. (Leibniz International Proceedings in Informatics (LIPIcs); Band 75).

Publikation: Kapitel in Büchern/Berichten/Konferenzbänden › Konferenzbeitrag › Begutachtung

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, Hrsg., 16th International Symposium on Experimental Algorithms (SEA 2017). Band 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

Zugriff auf Dokument

Fingerprint

Zitieren