Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
From MaRDI portal
Publication:412344
DOI10.1016/j.dam.2011.10.031zbMath1236.05127OpenAlexW1630345158MaRDI QIDQ412344
Frédéric Maffray, Vassilis Giakoumakis, Andreas Brandstädt
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
perfect graphsefficient algorithmsclique separator decompositionhole-free and diamond-free graphshole-free and paraglider-free graphs
Related Items
One-three join: a graph operation and its consequences ⋮ Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Colouring diamond-free graphs ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ On the chromatic number of (\(P_6\), diamond)-free graphs ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ 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 ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ Strong cliques in diamond-free graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On graphs without a \(C_{4}\) or a diamond
- On distance-3 matchings and induced matchings
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- On rigid circuit graphs
- On algorithms for (\(P_5\), gem)-free graphs
- The strong perfect graph theorem
- New applications of clique separator decomposition for the maximum weight stable set problem
- Characterising \((k,\ell )\)-leaf powers
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Simplicial powers of graphs
- Decomposition by clique separators
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- 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 the structure of (\(P_{5}\),\,gem)-free graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Finding a maximum induced matching in weakly chordal graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Algorithmic graph theory and perfect graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Doubly lexical ordering of dense 0--1 matrices
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Doubly Lexical Orderings of Matrices
- Three Partition Refinement Algorithms
- Perfect Elimination and Chordal Bipartite Graphs
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Even-hole-free graphs: A survey
