A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
DOI10.1016/S0166-218X(99)00146-8zbMATH Open0940.05064OpenAlexW2040405987WikidataQ127908675 ScholiaQ127908675MaRDI QIDQ1962057FDOQ1962057
Authors: Hajo Broersma, Elias Dahlhaus, Ton Kloks 
Publication date: 19 July 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00146-8
Recommendations
- scientific article; zbMATH DE number 1107726
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- Linear-time algorithm for paired-domination on distance-hereditary graphs
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- Treewidth and minimum fill-in on permutation graphs in linear time
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Graph-Theoretic Concepts in Computer Science
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- Exact Algorithms for Treewidth and Minimum Fill-In
algorithmscomplexitytreewidthcliquetree decompositiondistance hereditary graphminimum fill-in problem
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)
Cites Work
- Incidence matrices and interval graphs
- Complexity of Finding Embeddings in a k-Tree
- On rigid circuit graphs
- Distance-hereditary graphs
- Treewidth. Computations and approximations
- Triangulated graphs and the elimination process
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Computing the Minimum Fill-In is NP-Complete
- Treewidth and Pathwidth of Permutation Graphs
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- Treewidth of Chordal Bipartite Graphs
- The pathwidth and treewidth of cographs
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- How to use the minimal separators of a graph for its chordal triangulation
- Completely separable graphs
- Treewidth of Circular-Arc Graphs
- Approximating the bandwidth for asteroidal triple-free graphs
- Title not available (Why is that?)
- TREEWIDTH OF CIRCLE GRAPHS
- Title not available (Why is that?)
Cited In (22)
- Characterizing and computing minimal cograph completions
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
- Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
- Twin-distance-hereditary digraphs
- Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs
- Minimal triangulations of graphs: a survey
- Characterizing and Computing Minimal Cograph Completions
- Title not available (Why is that?)
- Equistable distance-hereditary graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Strongly chordal and chordal bipartite graphs are sandwich monotone
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
- A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
- Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
- Triangulating graphs with few \(P_4\)'s
- Laminar structure of ptolemaic graphs with applications
- Faster and enhanced inclusion-minimal cograph completion
This page was built for publication: A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962057)
