×

zbMATH — the first resource for mathematics

Jdrasil: a modular library for computing tree decompositions. (English) Zbl 1433.68275
Iliopoulos, Costas S. (ed.) et al., 16th international symposium on experimental algorithms, SEA 2017, London, UK, June 21–23, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 75, Article 28, 21 p. (2017).
Summary: 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.
For the entire collection see [Zbl 1372.68011].

MSC:
68R10 Graph theory (including graph drawing) in computer science
68-04 Software, source code, etc. for problems pertaining to computer science
68W99 Algorithms in computer science
PDF BibTeX XML Cite
Full Text: DOI