文章基本信息

标题：Jdrasil: A Modular Library for Computing Tree Decompositions
本地全文：下载
作者：Max Bannach ; Sebastian Berndt ; Thorsten Ehlers 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：75
页码：28:1-28:21
DOI：10.4230/LIPIcs.SEA.2017.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：tree width; algorithmic library; experimental evaluation