A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

1996/12/01 by Hans L. Bodlaender · 35 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Graph Labeling and Dimension Problems #Treewidth #Combinatorics #Pathwidth #Tree decomposition #Partial k-tree #Mathematics #Tree-depth #Time complexity #Discrete mathematics #Path (computing) #Constant (computer programming) #Planar graph #Chordal graph #Clique-sum #1-planar graph #Graph #Algorithm #Computer science #Line graph

paper · doi:10.1137/s0097539793251219

openalex publication_date 1996/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03

Abstract

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.

Citations

• Dynamic programming on graphs with bounded treewidth
• The NP-completeness column: An ongoing guide

Cited by

• An annotated bibliography on guaranteed graph searching
• Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
• Deciding first-order properties of locally tree-decomposable structures
• A c^k n 5-Approximation Algorithm for Treewidth
• An Improvement of Reed’s Treewidth Approximation
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth
• Approximation Algorithms for Treewidth
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• All Structured Programs Have Small Tree Width and Good Register Allocation
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Exact Algorithms for Treewidth and Minimum Fill-In
• Computing Optimal Linear Layouts of Trees in Linear Time
• On the Parameterized Complexity of Layered Graph Drawing
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Fixed-parameter algorithms for DAG Partitioning
• Inapproximability of Treewidth and Related Problems
• Clifford Algebras Meet Tree Decompositions
• 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
• The Graph Minor Algorithm with Parity Conditions
• Diameter and Treewidth in Minor-Closed Graph Families
• Kernelization: Theory of Parameterized Preprocessing
• Descriptive and Parameterized Complexity
• Graph Subcolorings: Complexity and Algorithms
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
• Edge-Coloring Partialk-Trees
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Linkless and flat embeddings in 3-space and the unknot problem
• Computing directed path-width and directed tree-width of recursively defined digraphs
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• Twin-width VIIIa: Delineation
• Branch-depth: Generalizing tree-depth of graphs
• Splitting a graph into disjoint induced paths or cycles
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Pathwidth [wikipedia]
• Tree decomposition [wikipedia]
• Treewidth [wikipedia]