Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs

MaRDI QIDQ5743477zbMATH OpenFDO

Authors Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095218

Mathematics Subject Classification ID

Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Separation routine and extended formulations for the stable set problem in claw-free graphs
• The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect
• Separation problems for the stable set polytope
• Solving the weighted stable set problem in claw-free graphs via decomposition
• scientific article; zbMATH DE number 6783420

Cites work

• scientific article; zbMATH DE number 1263275 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• A cutting plane algorithm for minimum perfect 2-matchings
• Branched polyhedral systems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• Edmonds polytopes and a hierarchy of combinatorial problems
• Geometric algorithms and combinatorial optimization
• Maximum matching and a polyhedron with 0,1-vertices
• Odd Minimum Cut-Sets and b-Matchings
• On maximal independent sets of vertices in claw-free graphs
• Projection, lifting and extended formulation integer and combinatorial optimization
• The structure of claw-free graphs

Cited in

(4)

• Separation routine and extended formulations for the stable set problem in claw-free graphs
• Lifts for Voronoi cells of lattices
• Stable sets and graphs with no even holes
• On stable cutsets in claw-free graphs and planar graphs

This page was built for publication: Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs

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