ON THE MULTIWAY CUT POLYHEDRON

被引：51

作者：

CHOPRA, S ^{[1
]}

RAO, MR ^{[1
]}

机构：

[1] NYU,LEONARD N STERN SCH BUSINESS,NEW YORK,NY 10006

来源：

NETWORKS | 1991年 / 21卷 / 01期

关键词：

D O I：

10.1002/net.3230210106

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given a graph G = (V,E) and a set N-subset-of-V, we consider the problem of finding a minimum-weight multiway cut that separates each pair of nodes in N. In this paper we give an integer programming formulation of this problem and study the associated polyhedron. We give some computational results to support the strength of our facets. We also give some efficiently solvable instances.

引用

页码：51 / 89

页数：39

共 14 条

[1]

BACHEM A, 1982, MODERN APPLIED MATH, P51

[2] AN APPLICATION OF COMBINATORIAL OPTIMIZATION TO STATISTICAL PHYSICS AND CIRCUIT LAYOUT DESIGN [J].

BARAHONA, F ;

GROTSCHEL, M ;

JUNGER, M ;

REINELT, G .

OPERATIONS RESEARCH, 1988, 36 (03) :493-513

[3]

BONDY JA, 1976, GRAPH THEORY APPLICA

[4]

CHOPRA S, UNPUB BRANCH CUT ALG

[5]

Ford L., 1962, FLOWS NETWORKS, V71, P1059, DOI 10.2307/2311955

[6] A CUTTING PLANE ALGORITHM FOR THE LINEAR ORDERING PROBLEM [J].

GROTSCHEL, M ;

JUNGER, M ;

REINELT, G .

OPERATIONS RESEARCH, 1984, 32 (06) :1195-1220

[7]

GROTSCHEL M, 1987, 6 U AUGSB I MATH REP

[8]

GROTSCHEL M, 1987, 18 U AUGSB I MATH RE

[9]

GROTSCHEL M, 1988, 73 U AUGSB I MATH RE

[10]

GROTSCHEL M, 1987, 9 U AUGSB I MATH REP

← 1 2 →