Treewidth for graphs with small chordality

DOI10.1016/S0166-218X(97)00031-0zbMath0895.68113MaRDI QIDQ1372729

Hans L. Bodlaender, Dimitrios M. Thilikos

Publication date: 7 January 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

treewidth; pathwidth; \(k\)-chordal graphs

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

Related Items

Fugitive-search games on graphs and related parameters, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for clustering graphs with dominating diametral path
• Finding and counting given length cycles
• Graph minors. III. Planar tree-width
• Weakly triangulated graphs
• Graph minors. I. Excluding a forest
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Min Cut is NP-complete for edge weighted trees
• On the pathwidth of chordal graphs
• Fugitive-search games on graphs and related parameters
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• A Separator Theorem for Planar Graphs
• Generalized Nested Dissection
• Applications of a Planar Separator Theorem
• A Sufficient Condition for Backtrack-Free Search
• Treewidth of Circular-Arc Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Asteroidal Triple-Free Graphs
• Parallel algorithms with optimal speedup for bounded treewidth
• The Pathwidth and Treewidth of Cographs
• Treewidth of Chordal Bipartite Graphs
• Treewidth and Pathwidth of Permutation Graphs
• TREEWIDTH OF CIRCLE GRAPHS
• The Linkage of a Graph
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Transitiv orientierbare Graphen
• k-Degenerate Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth