Treewidth for graphs with small chordality

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

Dimitrios M. Thilikos, Hans L. Bodlaender

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

treewidthpathwidth\(k\)-chordal graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items

Induced 2-regular subgraphs in \(k\)-chordal cubic graphs, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, As Time Goes By: Reflections on Treewidth for Temporal Graphs, Tree-decompositions with bags of small diameter, Tree-width dichotomy, Treewidth distance on phylogenetic trees, Boxicity and treewidth, Metric Dimension of Bounded Width Graphs, A Dirac-type characterization of \(k\)-chordal graphs, Fugitive-search games on graphs and related parameters, Some results on connected vertex separators, Unnamed Item, Edge-treewidth: algorithmic and combinatorial properties, Tree-Width and Optimization in Bounded Degree Graphs, Boundary Classes of Planar Graphs, Dominating induced matchings in graphs without a skew star, \(k\)-chordal graphs: from cops and robber to compact routing via treewidth, On the tree-width of even-hole-free graphs, Coloring vertices of claw-free graphs in three colors, Connected graph searching in chordal graphs, Recent developments on graphs of bounded clique-width, Partitioning the vertices of a cubic graph into two total dominating sets, An improved algorithm for the longest induced path problem on \(k\)-chordal graphs, Graphs without large apples and the maximum weight independent set problem, Maximum independent sets in subcubic graphs: new results, A spectral lower bound for the treewidth of a graph and its consequences, Unnamed Item, In absence of long chordless cycles, large tree-width becomes a local phenomenon, Metric Dimension of Bounded Tree-length Graphs

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