Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
DOI10.1016/J.DAM.2014.11.018zbMATH Open1311.05182OpenAlexW1965381228MaRDI QIDQ2341752FDOQ2341752
Authors: Anne Berry, Andreas Brandstädt, Vassilis Giakoumakis, Frédéric Maffray 
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
Recommendations
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Recognition algorithm for diamond-free graphs
- Finding houses and holes in graphs
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
algorithmsgraph classesminimal triangulationsclique separator decompositiondiamond-free graphshole-free graphsLexBFSrecognition time bound
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Topics in Intersection Graph Theory
- Title not available (Why is that?)
- Decomposition by clique separators
- On rigid circuit graphs
- Doubly lexical ordering of dense 0--1 matrices
- Three Partition Refinement Algorithms
- Optimal decomposition by clique separators
- Minimal triangulations of graphs: a survey
- Algorithmic Aspects of Vertex Elimination on Graphs
- Weakly triangulated graphs
- Recognizing weakly triangulated graphs by edge separability
- Title not available (Why is that?)
- Doubly Lexical Orderings of Matrices
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Dividing a Graph into Triconnected Components
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Algorithms for weakly triangulated graphs
- Treewidth of Chordal Bipartite Graphs
- Characterizations and algorithmic applications of chordal graph embeddings
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Improved algorithms for weakly chordal graphs
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Separability generalizes Dirac's theorem
- Graph extremities defined by search algorithms
- An introduction to clique minimal separator decomposition
- A peep through the looking glass: articulation points in lattices
- A Unified View of Graph Searching
- Even-hole-free graphs: A survey
- Triangulation and clique separator decomposition of claw-free graphs
- On graphs without a \(C_{4}\) or a diamond
- Minimal fill in O(\(n^{2.69}\)) time
- LexBFS-orderings and powers of chordal graphs
- Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
- Title not available (Why is that?)
- Detecting holes and antiholes in graphs
Cited In (6)
- Approximation of knapsack problems with conflict and forcing graphs
- Strong cliques in diamond-free graphs
- Graphs with at most two moplexes
- Revisiting decomposition by clique separators
- Maximum weight independent sets in odd-hole-free graphs without dart or without bull
- Induced subgraphs of bounded treewidth and the container method
Uses Software
This page was built for publication: Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2341752)
