THE COMPLEXITY OF MULTITERMINAL CUTS

被引：404

作者：

DAHLHAUS, E

JOHNSON, DS

PAPADIMITRIOOU, CH

SEYMOUR, PD

YANNAKAKIS, M

机构：

[1] UNIV BONN, W-5300 BONN 1, GERMANY

[2] BELL COMMUN RES INC, MORRISTOWN, NJ 07960 USA

[3] AT&T BELL LABS, MURRAY HILL, NJ 07974 USA

[4] UNIV CALIF SAN DIEGO, DEPT COMP SCI & ENGN, LA JOLLA, CA 92093 USA

来源：

SIAM JOURNAL ON COMPUTING | 1994年 / 23卷 / 04期

关键词：

NP-COMPLETENESS; NETWORK FLOW; PARTITIONING; PLANAR GRAPHS;

D O I：

10.1137/S0097539792225297

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the multiterminal cut problem one is given an edge-weighted graph and a subset of the vertices called terminals, and is asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the mincut, max-flow problem, and can be solved in polynomial time. It is shown that the problem becomes NP-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. A simple approximation algorithm for arbitrary graphs that is g guaranteed to come within a factor of 2 - 2/k of the optimal cut weight is also described.

引用

页码：864 / 894

页数：31

共 24 条

[1] ARORA S, 1992, AN S FDN CO, P14
[2] ON THE MULTIWAY CUT POLYHEDRON
CHOPRA, S
RAO, MR
[J]. NETWORKS, 1991, 21 (01) : 51 - 89
[3] Cunningham WH, 1991, DIMACS SERIES DISCRE, V5, P105, DOI 10.1090/dimacs/005/07
[4] DAHLHAUS E, 1983, COMPLEXITY MULTIWAY
[5] ERDOS PL, IN PRESS ADV APPL MA
[6] ERDOS PL, 1992, INTEGER PROGRAMMING, P334
[7] Ford L., 1962, FLOWS NETWORKS, V71, P1059, DOI 10.2307/2311955
[8] FREDERICKSON GN, 1987, SIAM J COMPUT, V16, P1004, DOI 10.1137/0216064
[9] Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
[10] Garey M.R., 1979, COMPUTERS INTRACTABI, V174

← 1 2 3 →