Treewidth computations I. Upper bounds

For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. This paper gives an overview of several upper bound heuristics that have been proposed and tested for the problem of determining the treewidth of a graph and finding tree decompositions. Each of the heuristics produces tree decompositions whose width may be larger than the optimal width. However, experiments show that in many cases, the heuristics give tree decompositions whose width is close to the exact treewidth of the input graphs.

Authors

• Hans L. Bodlaender
• Arie M.C.A. Koster

Keywords

• Treewidth
• Upper bounds
• Heuristics
• Approximation algorithms
• Graph algorithms