Critical facets of the stable set polytope

DOI10.1007/S004930170005MaRDI QIDQ873649zbMATH OpenOpenAlexFDO

Authors L. Lipták, László Lovász

Publication date 29 March 2007

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930170005

zbMATH Keywords

critical facets

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Facets with fixed defect of the stable set polytope
• Weighted graphs defining facets: A connection between stable set and linear ordering polytopes
• Stability critical graphs and ranks facets of the stable set polytope
• scientific article; zbMATH DE number 1953190
• On the stable set polytope of a series-parallel graph

Cited in

(15)

• On a weighted generalization of α-critical graphs
• Wheel inequalities for stable set polytopes
• Facets with fixed defect of the stable set polytope
• How to recycle your facets
• On the facets of lift-and-project relaxations under graph operations
• Stable set polytopes in a higher dimensional space
• The stable set polytope of icosahedral graphs
• The strength of Dantzig-Wolfe reformulations for the stable set and related problems
• Stability critical graphs and ranks facets of the stable set polytope
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• Weighted graphs defining facets: A connection between stable set and linear ordering polytopes
• On the facets of the lift-and-project relaxations of graph subdivisions
• General cut-generating procedures for the stable set polytope
• The biorder polytope
• Facets of the linear ordering polytope: a unification for the fence family through weighted graphs

This page was built for publication: Critical facets of the stable set polytope

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