A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
A graph \(G\) is a distance hereditary graph if for each pair of vertices \(v,w\in V_G\), their distance in all induced subgraphs of \(G\) that contain \(v\) and \(w\) is the same. The minimum fill-in problem is to find a chordal supergraph of a given graph with the minimum number of edges. The treewidth problem is to find a chordal supergraph of a given graph with the minimum maximum clique size, or alternatively, to find a tree decomposition of minimum width. This paper is one of a collection of papers that address the complexity of the minimum fill-in or treewidth problem for special graphs. It is shown that both problems can be solved in linear time when the input graph is distance hereditary. As a first step in the algorithms, a representation of the graph by a fragment tree is made.
- 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
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- Approximating the bandwidth for asteroidal triple-free graphs
- Completely separable graphs
- Complexity of Finding Embeddings in a k-Tree
- Computing the Minimum Fill-In is NP-Complete
- Distance-hereditary graphs
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- How to use the minimal separators of a graph for its chordal triangulation
- scientific article; zbMATH DE number 1107726 (Why is no real title available?)
- scientific article; zbMATH DE number 2102752 (Why is no real title available?)
- Incidence matrices and interval graphs
- On rigid circuit graphs
- The pathwidth and treewidth of cographs
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- Treewidth and Pathwidth of Permutation Graphs
- Treewidth of Chordal Bipartite Graphs
- TREEWIDTH OF CIRCLE GRAPHS
- Treewidth of Circular-Arc Graphs
- Treewidth. Computations and approximations
- Triangulated graphs and the elimination process
- Laminar structure of ptolemaic graphs with applications
- Triangulating graphs with few \(P_4\)'s
- Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
- 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
- Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
- Linear rank-width of distance-hereditary graphs
- Characterizing and Computing Minimal Cograph Completions
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- scientific article; zbMATH DE number 841632 (Why is no real title available?)
- Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
- scientific article; zbMATH DE number 7310078 (Why is no real title available?)
- Computational aspects of treewidth for graph
- Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
- Twin-distance-hereditary digraphs
- Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
- 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
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)
