SEPARATING FROM THE DOMINANT OF THE SPANNING TREE POLYTOPE

被引：36

作者：

BARAHONA, F

机构：

[1] IBM T.J. Watson Research Center, Yorktown Heights

来源：

OPERATIONS RESEARCH LETTERS | 1992年 / 12卷 / 04期

关键词：

SPANNING TREE POLYHEDRON; SEPARATION PROBLEM;

D O I：

10.1016/0167-6377(92)90045-5

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study the separation problem for the partition inequalities that define the dominant of the spanning tree polytope of a graph G = (V, E). We show that a most violated inequality can be found by solving at most absolute value of V maximum flow problems. Cunningham (1985) had solved this as a sequence of Absolute value of E maximum flow problems.

引用

页码：201 / 203

页数：3