We are three students of Computing Science attending the master Applied Computing Science at University of Utrecht. Before we start with our master thesis we did an experimentation project on computing the treewidth and tree decompositions. In co-operation with our lecturer Hans Bodlaender we compared various algorithms and coded a library. The results of this project are posted on this website.
We presented our results at the TACO day, a research project on Treewidth and Combinatorial Optimization. It is in cooperation between the Institute for Information and Computing Sciences of Utrecht University and the Department of Quantitative Economics of Maastricht University.
Download our presentation.
Abstract: There are many algorithms to compute an upperbound, a lowerbound or the exact treewidth of a graph. We have implemented a lot of upperbound and lowerbound heuristics and two exact algorithms (a Dynamic Programming and a Branch and Bound algorithm). This report compares the different kind of algorithms and shows that some algorithms are preferred. From our results with the lowerbound algorithms we can conclude that the Least-C variant for Maximum Minimum Degree almost dominates the other algorithms. For the upperbounds, we conclude that Greedy-FillIn is best. TreewidthDP is quite fast on most of the tested graphs, but runs out of memory on large graphs. If TreewidthDP can not run with the available amount of memory one could use QuickBB, which is slower, but uses less memory. We investigated the effects of the Memorization method on QuickBB suggested by Van Hoesel and found that it improved the algorithm with at least factor 15.
Here we provide you the sofware we developed. You can download the file here.
This zipfile contains:
In the near future we'll expand the information on this website.
In the mean time you have a look at the FAQ.
Thomas van Dijk (firstname.lastname@example.org)
Jan-Pieter van den Heuvel (email@example.com)
Wouter slob (firstname.lastname@example.org)