A linear-time algorithm for finding tree-decompositions of small treewidth. (English) Zbl 0864.68074

Bodlaender, Hans L.

SIAM J. Comput. 25, No. 6, 1305-1317 (1996).

Summary: We give for constant \(k\) a linear-time algorithm that, given a graph \(G=(V,E)\), determines whether the treewidth of \(G\) is at most \(k\) and, if so, finds a tree-decomposition of \(G\) with treewidth at most \(k\). A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at most some constant \(k\).

MSC:

68R10	Graph theory (including graph drawing) in computer science
05C85	Graph algorithms (graph-theoretic aspects)
05C05	Trees

Keywords:

graph algorithms; graph minors; tree-decomposition; pathwidth