×

On Grötschel-Lovász-Schrijver’s relaxation of stable set polytopes. (English) Zbl 1140.90514

Summary: 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.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI