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

DOI10.1016/j.orl.2011.04.002zbMath1225.05230OpenAlexW1998010248MaRDI QIDQ635519

C. Snels, Gianpaolo Oriolo, Yuri Faenza

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)

Related Items (2)

Asymptotics of the chromatic number for quasi-line graphs ⋮ On the recognition of fuzzy circular interval graphs

Cites Work

• Unnamed Item
• On the recognition of fuzzy circular interval graphs
• The strong perfect graph theorem
• The stable set polytope of quasi-line graphs
• Claw-free graphs. V. Global structure
• 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
• Bull-free Berge graphs are perfect
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Coloring quasi-line graphs
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs

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