A POLYNOMIAL ALGORITHM FOR THE KAPPA-CUT PROBLEM FOR FIXED KAPPA

被引：166

作者：

GOLDSCHMIDT, O

HOCHBAUM, DS

机构：

[1] UNIV CALIF BERKELEY, SCH BUSINESS ADM, BERKELEY, CA 94720 USA

[2] UNIV CALIF BERKELEY, DEPT IEOR, BERKELEY, CA 94720 USA

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1994年 / 19卷 / 01期

关键词：

CLUSTERING; MIN-CUT; MAX-FLOW; COMPLEXITY; POLYNOMIAL ALGORITHM; KAPPA-CUT;

D O I：

10.1287/moor.19.1.24

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for an arbitrary k and its version involving fixing a vertex in each component is NP-hard even for k = 3. We present a polynomial algorithm for k fixed, that runs in O(n(k2/2-3k/2+4)T(n, m)) steps, where T(n, m) is the running time required to find the minimum (s, t)-cut on a graph with n vertices and m edges.

引用

页码：24 / 37

页数：14

共 16 条

[1]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[2] OPTIMAL ATTACK AND REINFORCEMENT OF A NETWORK [J].