A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
From MaRDI portal
Publication:1962057
DOI10.1016/S0166-218X(99)00146-8zbMath0940.05064MaRDI QIDQ1962057
Ton Kloks, Elias Dahlhaus, Hajo J. Broersma
Publication date: 19 July 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
complexity; algorithms; treewidth; tree decomposition; clique; distance hereditary graph; minimum fill-in problem
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, Minimal triangulations of graphs: a survey, Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs, A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs, Characterizing and computing minimal cograph completions, Laminar structure of ptolemaic graphs with applications, Triangulating graphs with few \(P_4\)'s, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Equistable distance-hereditary graphs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Characterizing and Computing Minimal Cograph Completions
Cites Work
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- Completely separable graphs
- Distance-hereditary graphs
- Treewidth. Computations and approximations
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- Complexity of Finding Embeddings in a k-Tree
- Computing the Minimum Fill-In is NP-Complete
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- Treewidth of Circular-Arc Graphs
- How to use the minimal separators of a graph for its chordal triangulation
- Treewidth of Chordal Bipartite Graphs
- Treewidth and Pathwidth of Permutation Graphs
- TREEWIDTH OF CIRCLE GRAPHS
- The pathwidth and treewidth of cographs
- Approximating the bandwidth for asteroidal triple-free graphs
