Treewidth for graphs with small chordality
From MaRDI portal
Publication:1372729
DOI10.1016/S0166-218X(97)00031-0zbMATH Open0895.68113MaRDI QIDQ1372729FDOQ1372729
Authors: 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
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Generalized Nested Dissection
- Applications of a Planar Separator Theorem
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Min Cut is NP-complete for edge weighted trees
- Complexity of Finding Embeddings in a k-Tree
- A Sufficient Condition for Backtrack-Free Search
- Title not available (Why is that?)
- k-Degenerate Graphs
- Finding and counting given length cycles
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Graph minors. II. Algorithmic aspects of tree-width
- A Separator Theorem for Planar Graphs
- Transitiv orientierbare Graphen
- Asteroidal Triple-Free Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Weakly triangulated graphs
- An approximation algorithm for clustering graphs with dominating diametral path
- Graph minors. I. Excluding a forest
- On the pathwidth of chordal graphs
- Fugitive-search games on graphs and related parameters
- Parallel algorithms with optimal speedup for bounded treewidth
- The Pathwidth and Treewidth of Cographs
- Treewidth and Pathwidth of Permutation Graphs
- Graph minors. III. Planar tree-width
- Treewidth of Chordal Bipartite Graphs
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Treewidth of Circular-Arc Graphs
- The Linkage of a Graph
- TREEWIDTH OF CIRCLE GRAPHS
Cited In (39)
- Treewidth of graphs with balanced separations
- Induced 2-regular subgraphs in \(k\)-chordal cubic graphs
- Coloring vertices of claw-free graphs in three colors
- Tree-width dichotomy
- A Dirac-type characterization of \(k\)-chordal graphs
- On 3-degree 4-chordal graphs
- Connected graph searching in chordal graphs
- Graphs without large apples and the maximum weight independent set problem
- On the chordality of a graph
- Boundary Classes of Planar Graphs
- Recent developments on graphs of bounded clique-width
- Graphs with at most two moplexes
- Characterizing Graphs of Small Carving-Width
- Tree-decompositions of small pathwidth
- Treewidth distance on phylogenetic trees
- Partitioning the vertices of a cubic graph into two total dominating sets
- In absence of long chordless cycles, large tree-width becomes a local phenomenon
- Treewidth of Chordal Bipartite Graphs
- Dominating induced matchings in graphs without a skew star
- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- Edge-treewidth: algorithmic and combinatorial properties
- On the tree-width of even-hole-free graphs
- On the pathwidth of chordal graphs
- Tree-width and circumference of graphs
- Fugitive-search games on graphs and related parameters
- Results on hyperbolicity in graphs: a survey
- Title not available (Why is that?)
- Metric Dimension of Bounded Tree-length Graphs
- Chordal bipartite graphs of bounded tree- and clique-width
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- A spectral lower bound for the treewidth of a graph and its consequences
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- Metric dimension of bounded width graphs
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Some results on connected vertex separators
- On balanced separators, treewidth, and cycle rank
- Boxicity and treewidth
- Tree-Width and Optimization in Bounded Degree Graphs
- Tree-decompositions with bags of small diameter
This page was built for publication: Treewidth for graphs with small chordality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1372729)
