The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
A Linear-Time Algorithm for Finding Tree-decompositions of Small Trewidth
Hans L. Bodlaender,
Pages. 1305-1317
Abstract In this paper, we give for constant $k$ a linear-time algorithm that, given a graph $G=(V,E)$, determines whether the tree-width of $G$ is at most $k$ and, if so, finds a tree-decomposition of $G$ with tree-width 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 path-width at most some constant $k$.
Contents 1. Introduction
1.1. Background
1.2. Main idea of algorithm
2. Definitions and preliminary results
3. Friendly, high-degree, and low-degree vertices
4. Simplicial vertices
5. Main algorithm
6. Some details of the algorithm
7. Final remarks
Key words graph algorithms, treewidth, pathwidth, partial $k$-trees, graph minors.
Mathmatical Subject Classification 68R10, 05C85, 05C05