Treewidth: Computational Experiments
AbstractMany NP-complete graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed k, linear time algorithms exist to solve the decision problem ``treewidth at most k, their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 001.
Date of creation: 2002
Date of revision:
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/UMPublications.htm
operations research and management science;
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- repec:ner:maastr:urn:nbn:nl:ui:27-10511 is not listed on IDEAS
- Koster,A.M.C.A. & Hoesel,S.P.M.,van & Kolen,A.W.J., 1999. "Solving frequency assignment problems via tree-decomposition," Research Memoranda 036, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Charles Bollen).
If references are entirely missing, you can add them using this form.