Lifting facets of the cut polytope

Lifting facets of the cut polytope

0.00 Avg rating0 Votes
Article ID: iaor19911061
Country: Netherlands
Volume: 9
Issue: 5
Start Page Number: 341
End Page Number: 344
Publication Date: Sep 1990
Journal: Operations Research Letters
Authors:
Abstract:

The cut polytope PC(G) of a graph G is the convex hull of the incidence vectors of the edge sets of all cuts of G. The paper gives a sufficient condition for an inequality defining a facet of PC(G) to define a facet of the cut polytope of a graph containing G as an induced subgraph. The present result generalizes a result of Deza stating that if G is a complete graph with more than two vertices, then an inequlaity defines a facet of PC(G) if and only if it defines a facet of the cut polytope of every complete graph containing G.

Reviews

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