A tourist guide through treewidth. (English) Zbl 0804.68101

Bodlaender, Hans L.

Acta Cybern. 11, No. 1-2, 1-21 (1993).

Summary: A short overview is given of many recent results in algorithmic graph theory that deal with the notions treewidth and pathwidth. We discuss algorithms that find tree-decompositions, algorithms that use tree- decompositions to solve hard problems efficiently, graph minor theory, and some applications. The paper contains an extensive bibliography.

MSC:

68R10	Graph theory (including graph drawing) in computer science
05C85	Graph algorithms (graph-theoretic aspects)
00A15	Bibliographies for mathematics in general

Keywords:

algorithmic graph theory; treewidth; pathwidth; tree-decompositions; graph minor; bibliography