TreewidthLIB: A benchmark for algorithms for Treewidth and related graph problems. The notion of treewidth has played an important role in research in algorithmic graph theory in the past years. More recently, research has been done where the notion is also used in practical and experimental settings to solve graph problems. In many of these settings, algorithms are needed that generate tree decompositions with sufficiently small width, and that are sufficiently fast. In order to compare implementations of such algorithms, it would be helpful to have a large enough set of graphs for which computing their treewidth is relevant. TreewidthLIB is aimed at providing such a set of graphs: i.e., a collection of graphs that can be used as benchmark for the comparison of algorithms computing treewidth, tree decompositions, but also for algorithms that solve problems related to treewidth, like branchwidth or minimum fill-in.
Keywords for this software
References in zbMATH (referenced in 9 articles )
Showing results 1 to 9 of 9.
- Fafianie, Stefan; Bodlaender, Hans; Nederlof, Jesper: Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions (2015)
- Langer, Alexander; Reidl, Felix; Rossmanith, Peter; Sikdar, Somnath: Practical algorithms for MSO model-checking on tree-decomposable graphs (2014)
- Fafianie, Stefan; Bodlaender, Hans L.; Nederlof, Jesper: Speeding up dynamic programming with representative sets. An experimental evaluation of algorithms for Steiner Tree on tree decompositions (2013)
- Bodlaender, Hans L.; Koster, Arie M.C.A.: Treewidth computations. II. Lower bounds (2011)
- Bodlaender, Hans L.; Koster, Arie M.C.A.: Treewidth computations. I: Upper bounds (2010)
- Bodlaender, Hans L.; van Dijk, Thomas C.: A cubic kernel for feedback vertex set and loop cutset (2010)
- Chein, Michel; Mugnier, Marie-Laure: Graph-based knowledge representation. Computational foundations of conceptual graphs (2009)
- Bodlaender, Hans L.; Grigoriev, Alexander; Koster, Arie M.C.A.: Treewidth lower bounds with brambles (2008)
- Bodlaender, Hans L.; Koster, Arie M.C.A.: On the maximum cardinality search lower bound for treewidth (2007)