A New Facet Generating Procedure for the Stable Set Polytope

DOI10.1016/j.endm.2011.05.032zbMath1268.05216OpenAlexW2070265150MaRDI QIDQ2840706

Álinson S. Xavier, Manoel B. Campêlo

Publication date: 23 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2011.05.032

zbMATH Keywords

liftingstable set polytopefacetspolyhedral combinatorics

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

A strengthened general cut-generating procedure for the stable set polytope ⋮ On the complete set packing and set partitioning polytopes: properties and rank 1 facets ⋮ On the combinatorics of the 2-class classification problem ⋮ On the facets of lift-and-project relaxations under graph operations ⋮ Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope ⋮ General cut-generating procedures for the stable set polytope ⋮ A new lifting theorem for vertex packing

Cites Work

• Gear composition and the stable set polytope
• A one-to-one correspondence between colorings and stable sets
• Further facet generating procedures for vertex packing polytopes
• Compositions of Graphs and Polyhedra II: Stable Sets
• Facet Obtaining Procedures for Set Packing Problems
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra