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

DOI10.1016/J.ORL.2011.04.002MaRDI QIDQ635519zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• 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
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Bull-free Berge graphs are perfect
• Claw-free graphs. V. Global structure
• Coloring quasi-line graphs
• On the recognition of fuzzy circular interval 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
• The stable set polytope of quasi-line graphs
• The strong perfect graph theorem
• The structure of 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)