Approximating treewidth and pathwidth of some classes of perfect graphs

1992/01/01 by Ton Kloks, Hans L. Bodlaender, Hans Bodlaender · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Line graph #Mathematics #Partial k-tree #Pathwidth #Tree decomposition #Tree-depth #Treewidth

paper · doi:10.1007/3-540-56279-6_64

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/09 · crossref created 2012/02/26 · crossref deposited 2023/06/20 · crossref indexed 2024/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Citations

• The pathwidth and treewidth of cographs
• Linear time algorithms for NP-hard problems restricted to partial k-trees
• Normal hypergraphs and the perfect graph conjecture
• Permutation Graphs and Transitive Graphs
• The monadic second-order logic of graphs. I. Recognizable sets of finite graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey
• On rigid circuit graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Complexity of Finding Embeddings in a k-Tree
• Incidence matrices and interval graphs
• Finding approximate separators and computing tree width quickly
• Approximating treewidth, pathwidth, and minimum elimination tree height
• Algorithmic Graph Theory and Perfect Graphs

Cited by

• Pathwidth [wikipedia]