Treewidth computations I. Upper bounds |
| |
Authors: | Hans L Bodlaender Arie MCA Koster |
| |
Affiliation: | 1. Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands;2. Lehrstuhl II für Mathematik, RWTH Aachen University, Wüllnerstr. zwischen 5 und 7, D-52062 Aachen, Germany |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|