Stable sets in claw-free graphs: a journey through algorithms and polytopes

MaRDI QIDQ3109934zbMATH OpenFDO

Authors Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer, P. Ventura

Publication date 26 January 2012

zbMATH Keywords

claw-free graphweighted stable set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Solving the weighted stable set problem in claw-free graphs via decomposition
• scientific article; zbMATH DE number 6783420
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A reduction algorithm for the weighted stable set problem in claw-free graphs
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)

Cited in

(16)

• scientific article; zbMATH DE number 1187143 (Why is no real title available?)
• A reduction algorithm for the weighted stable set problem in claw-free graphs
• On facets of stable set polytopes of claw-free graphs with stability number 3
• scientific article; zbMATH DE number 7080199 (Why is no real title available?)
• The stable set polytope of claw-free graphs with stability number greater than three
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
• Robust algorithms for the stable set problem
• Total coloring and total matching: polyhedra and facets
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• The stable set problem: clique and nodal inequalities revisited
• 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
• scientific article; zbMATH DE number 7204318 (Why is no real title available?)
• Polyhedral results on the stable set problem in graphs containing even or odd pairs
• On stable cutsets in claw-free graphs and planar graphs
• On the facets of stable set polytopes of circular interval graphs

This page was built for publication: Stable sets in claw-free graphs: a journey through algorithms and polytopes

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