Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
DOI10.1016/j.dam.2014.11.018zbMath1311.05182OpenAlexW1965381228MaRDI QIDQ2341752
Vassilis Giakoumakis, Frédéric Maffray, Andreas Brandstädt, Anne Berry
Publication date: 28 April 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.11.018
algorithmsdiamond-free graphsgraph classesminimal triangulationsclique separator decompositionhole-free graphsLexBFSrecognition time bound
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (4)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- On graphs without a \(C_{4}\) or a diamond
- On rigid circuit graphs
- Weakly triangulated graphs
- Minimal triangulations of graphs: a survey
- Minimal fill in O(\(n^{2.69}\)) time
- Detecting holes and antiholes in graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Decomposition by clique separators
- LexBFS-orderings and powers of chordal graphs
- Characterizations and algorithmic applications of chordal graph embeddings
- Separability generalizes Dirac's theorem
- Graph extremities defined by search algorithms
- An introduction to clique minimal separator decomposition
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
- Algorithms for weakly triangulated graphs
- Optimal decomposition by clique separators
- Doubly lexical ordering of dense 0--1 matrices
- A Peep through the Looking Glass: Articulation Points in Lattices
- Improved algorithms for weakly chordal graphs
- A Unified View of Graph Searching
- Doubly Lexical Orderings of Matrices
- Three Partition Refinement Algorithms
- Algorithmic Aspects of Vertex Elimination on Graphs
- Topics in Intersection Graph Theory
- Dividing a Graph into Triconnected Components
- Treewidth of Chordal Bipartite Graphs
- Even-hole-free graphs: A survey
- Triangulation and Clique Separator Decomposition of Claw-Free Graphs
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
This page was built for publication: Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
