Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
DOI10.1016/J.DAM.2011.10.031zbMATH Open1236.05127OpenAlexW1630345158MaRDI QIDQ412344FDOQ412344
Authors: Andreas Brandstädt, Vassilis Giakoumakis, Frédéric Maffray 
Publication date: 4 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.031
Recommendations
efficient algorithmsperfect graphsclique separator decompositionhole-free and diamond-free graphshole-free and paraglider-free graphs
Cites Work
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Decomposition by clique separators
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Algorithmic graph theory and perfect graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Title not available (Why is that?)
- On rigid circuit graphs
- The strong perfect graph theorem
- Doubly lexical ordering of dense 0--1 matrices
- Three Partition Refinement Algorithms
- Title not available (Why is that?)
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Doubly Lexical Orderings of Matrices
- Perfect Elimination and Chordal Bipartite Graphs
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- On algorithms for (\(P_5\), gem)-free graphs
- New applications of clique separator decomposition for the maximum weight stable set problem
- Characterising \((k,\ell )\)-leaf powers
- Title not available (Why is that?)
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- Finding a maximum induced matching in weakly chordal graphs
- On distance-3 matchings and induced matchings
- Title not available (Why is that?)
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Simplicial powers of graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Even-hole-free graphs: A survey
- Title not available (Why is that?)
- On graphs without a \(C_{4}\) or a diamond
Cited In (17)
- Approximation of knapsack problems with conflict and forcing graphs
- Organizing the atoms of the clique separator decomposition into an atom tree
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- Strong cliques in diamond-free graphs
- Title not available (Why is that?)
- On the chromatic number of (\(P_6\), diamond)-free graphs
- Weighted independent sets in classes of \(P_6\)-free graphs
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- Complexity and polynomially solvable special cases of QUBO
- Disjoint clique cutsets in graphs without long holes
- Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
- Maximum weight independent sets in hole- and dart-free graphs
- One-three join: a graph operation and its consequences
- Colouring diamond-free graphs
- Weighted independent sets in a subclass of \(P_6\)-free graphs
- Maximum weight independent sets in odd-hole-free graphs without dart or without bull
- Induced subgraphs of bounded treewidth and the container method
This page was built for publication: Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412344)
