Treewidthlib

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.


References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Coudert, David; Mazauric, Dorian; Nisse, Nicolas: Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth (2016)
  2. Lodha, Neha; Ordyniak, Sebastian; Szeider, Stefan: A SAT approach to branchwidth (2016)
  3. 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)
  4. Langer, Alexander; Reidl, Felix; Rossmanith, Peter; Sikdar, Somnath: Practical algorithms for MSO model-checking on tree-decomposable graphs (2014)
  5. 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)
  6. Hvidevold, Eivind Magnus; Sharmin, Sadia; Telle, Jan Arne; Vatshelle, Martin: Finding good decompositions for dynamic programming on dense graphs (2012)
  7. Bodlaender, Hans L.; Koster, Arie M.C.A.: Treewidth computations. II. Lower bounds (2011)
  8. Bodlaender, Hans L.; Koster, Arie M.C.A.: Treewidth computations. I: Upper bounds (2010)
  9. Bodlaender, Hans L.; van Dijk, Thomas C.: A cubic kernel for feedback vertex set and loop cutset (2010)
  10. Chein, Michel; Mugnier, Marie-Laure: Graph-based knowledge representation. Computational foundations of conceptual graphs (2009)
  11. Samer, Marko; Veith, Helmut: Encoding treewidth into SAT (2009)
  12. Bodlaender, Hans L.; Grigoriev, Alexander; Koster, Arie M.C.A.: Treewidth lower bounds with brambles (2008)
  13. Bodlaender, Hans L.; Koster, Arie M.C.A.: On the maximum cardinality search lower bound for treewidth (2007)