zbMATH — the first resource for mathematics

Algorithmic aspects of tree width. (English) Zbl 1035.05090
Reed, Bruce A. (ed.) et al., Recent advances in algorithms and combinatorics. New York, NY: Springer (ISBN 0-387-95434-1/hbk). CMS Books Math./Ouvrages Math. SMC 11, 85-107 (2003).
The paper gives a survey on recent results on graph algorithms that use the notions of treewidth and tree decomposition. Examples of problems where dynamic programming and divide and conquer strategies are used to solve graph problems are given, and the notions of treewidth and tree decomposition are introduced, and equivalence with other definitions is shown. The paper discusses how to find tree decompositions of bounded width, and how to use them, with applications. Also, a forbidden subgraph characterization of graphs of bounded treewidth is shown.
For the entire collection see [Zbl 1005.00014].

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
90C39 Dynamic programming
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
05C83 Graph minors