Dynamic programming on graphs with bounded treewidth

1988/01/01 by Hans L. Bodlaender · 11 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Line graph #Mathematics #Optimization and Search Problems #Partial k-tree #Pathwidth #Time complexity #Tree decomposition #Tree-depth #Treewidth

paper · doi:10.1007/3-540-19488-6_110

crossref issued 1988/01/01 · crossref published 1988/01/01 · crossref published-print 1988/01/01 · openalex publication_date 1988/01/01 · crossref published-online 2005/05/31 · crossref created 2012/02/25 · crossref deposited 2021/12/30 · openalex created_date 2025/10/10 · crossref indexed 2026/04/16 · openalex updated_date 2026/07/29

Cited by

• Finding approximate separators and computing tree width quickly
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth
• Tree-width, path-width, and cutwidth
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• LP approximations to mixed-integer polynomial optimization problems
• Efficient Subgraph Matching
• Two strikes against perfect phylogeny
• Tree decomposition [wikipedia]
• Treewidth [wikipedia]