A linear-time algorithm for finding tree-decompositions of small treewidth

In this paper, 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 con...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1996-12, Vol.25 (6), p.1305-1317
Main Author: BODLAENDER, H. L
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Decomposition
Exact sciences and technology
Graph theory
Graphs
Information retrieval. Graph
Mathematics
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, 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$.
ISSN:0097-5397
1095-7111
DOI:10.1137/s0097539793251219