Approximating treewidth, pathwidth, and minimum elimination tree height

1992/01/01 by Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Interconnection Networks and Systems #Mathematics #Pathwidth #Tree decomposition #Tree-depth #Treewidth #Vertex (graph theory)

paper · doi:10.1007/3-540-55121-2_1

crossref issued 1992/01/01 · crossref published 1992/01/01 · crossref published-print 1992/01/01 · openalex publication_date 1992/01/01 · crossref published-online 2005/06/05 · crossref created 2012/02/26 · crossref deposited 2020/11/17 · crossref indexed 2025/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Citations

• The pathwidth and treewidth of cographs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• Complexity of Finding Embeddings in a k-Tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• Nested Dissection of a Regular Finite Element Mesh
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

Cited by

• Approximating treewidth and pathwidth of some classes of perfect graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Pathwidth [wikipedia]