On Grötschel–Lovász–Shrijver's relaxation of stable set polytopes

On Grötschel–Lovász–Shrijver's relaxation of stable set polytopes

0.00 Avg rating0 Votes
Article ID: iaor20031627
Country: Japan
Volume: 45
Issue: 3
Start Page Number: 285
End Page Number: 292
Publication Date: Sep 2002
Journal: Journal of the Operations Research Society of Japan
Authors: ,
Keywords: graphs
Abstract:

Grötschel, Lovász and Schrijver introduced a convex set containing the stable set polytope of a graph. They proved that the set is a polytope if and only if the corresponding graph is perfect. In this paper, we give an alternative proof of the fact based on a new representation of the convex set described by infinitely many convex quadratic inequalities.

Reviews

Required fields are marked *. Your email address will not be published.