LIFTING FACETS OF THE CUT POLYTOPE

被引：9

作者：

DESIMONE, C

机构：

[1] CNR,IAC,I-00161 ROME,ITALY

[2] RUTGERS STATE UNIV,RUTCOR,NEW BRUNSWICK,NJ 08903

来源：

OPERATIONS RESEARCH LETTERS | 1990年 / 9卷 / 05期

关键词：

facet; graph; lifting; polyhedron;

D O I：

10.1016/0167-6377(90)90029-5

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. We give 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. Our result generalizes a result of Deza stating that if G is a complete graph with more than two vertices, then an inequality defines a facet of Pc(G) if and only if it defines a facet of the cut polytope of every complete graph containing G. © 1990.

引用

页码：341 / 344

页数：4