A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)

DOI10.1016/J.ORL.2011.04.002zbMATH Open1225.05230OpenAlexW1998010248MaRDI QIDQ635519FDOQ635519

Authors: C. Snels, Yuri Faenza, Gianpaolo Oriolo 

Publication date: 19 August 2011

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/181875

Recommendations

• An algorithm for finding homogeneous pairs
• A transformation which preserves the clique number
• Reconfiguring independent sets in claw-free graphs
• Even pairs in claw-free perfect graphs
• A reduction algorithm for the weighted stable set problem in claw-free graphs

zbMATH Keywords

reductionsgraph invariantsproper and homogeneous pairs of cliques

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• The strong perfect graph theorem
• Claw-free graphs. V. Global structure
• The structure of claw-free graphs
• The stable set polytope of quasi-line graphs
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Bull-free Berge graphs are perfect
• On the recognition of fuzzy circular interval graphs
• Coloring quasi-line graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Some classical combinatorial problems on circulant and claw-free graphs: The isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs

Cited In (1)

• On the recognition of fuzzy circular interval graphs

This page was built for publication: A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q635519)