License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.28
URN: urn:nbn:de:0030-drops-76051
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7605/
Go to the corresponding LIPIcs Volume Portal


Bannach, Max ; Berndt, Sebastian ; Ehlers, Thorsten

Jdrasil: A Modular Library for Computing Tree Decompositions

pdf-format:
LIPIcs-SEA-2017-28.pdf (0.6 MB)


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.

BibTeX - Entry

@InProceedings{bannach_et_al:LIPIcs:2017:7605,
  author =	{Max Bannach and Sebastian Berndt and Thorsten Ehlers},
  title =	{{Jdrasil: A Modular Library for Computing Tree Decompositions}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7605},
  URN =		{urn:nbn:de:0030-drops-76051},
  doi =		{10.4230/LIPIcs.SEA.2017.28},
  annote =	{Keywords: tree width, algorithmic library, experimental evaluation}
}

Keywords: tree width, algorithmic library, experimental evaluation
Seminar: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 03.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI