Gear composition and the stable set polytope

DOI10.1016/j.orl.2008.01.003zbMath1162.05356OpenAlexW2089330414MaRDI QIDQ1003487

Anna Galluccio, Paolo Ventura, Claudio Gentile

Publication date: 4 March 2009

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

Full work available at URL: https://doi.org/10.1016/j.orl.2008.01.003

zbMATH Keywords

stable set polytopepolyhedral combinatoricsclaw-free graphsgraph composition

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ 2-clique-bond of stable set polyhedra ⋮ Unnamed Item ⋮ 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 ⋮ Strengthened clique-family inequalities for the stable set polytope ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs ⋮ A New Facet Generating Procedure for the Stable Set Polytope ⋮ A new lifting theorem for vertex packing ⋮ On the Stable Set Polytope of Claw-Free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
• Claw-free graphs. IV: Decomposition theorem
• The stable set polytope of quasi-line graphs
• On the stable set polytope of a series-parallel graph
• On maximal independent sets of vertices in claw-free graphs
• On stable set polyhedra for K//(1,3)free graphs
• Geometric algorithms and combinatorial optimization
• A class of facet producing graphs for vertex packing polyhedra
• A strengthening of Ben Rebea's lemma
• The rank facets of the stable set polytope for claw-free graphs
• On certain polytopes associated with graphs
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs
• Claw-free graphs. VII. Quasi-line graphs
• Further facet generating procedures for vertex packing polytopes
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Gear composition and the stable set polytope