zbMATH — the first resource for mathematics

Discovering treewidth. (English) Zbl 1117.68451
Vojtáš, Peter (ed.) et al., SOFSEM 2005: Theory and practice of computer science. 31st conference on current trends in theory and practice of computer science, Liptovský Ján, Slovakia, January 22–28, 2005. Proceedings. Berlin: Springer (ISBN 3-540-24302-X/pbk). Lecture Notes in Computer Science 3381, 1-16 (2005).
Summary: Treewidth is a graph parameter with several interesting theoretical and practical applications. This survey reviews algorithmic results on determining the treewidth of a given graph, and finding a tree decomposition of small width. Both theoretical results, establishing the asymptotic computational complexity of the problem, as experimental work on heuristics (both for upper bounds as for lower bounds), preprocessing, exact algorithms, and postprocessing are discussed.
For the entire collection see [Zbl 1069.68013].

68R10 Graph theory (including graph drawing) in computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI