Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences

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

zbMATH Keywords

perfect graphsefficient algorithmsclique separator decompositionhole-free and diamond-free graphshole-free and paraglider-free graphs

Mathematics Subject Classification ID

Perfect graphs (05C17) Graph designs and isomorphic decomposition (05C51)

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