A POLYNOMIAL ALGORITHM FOR THE KAPPA-CUT PROBLEM FOR FIXED KAPPA
成果类型：
Article
署名作者：
GOLDSCHMIDT, O; HOCHBAUM, DS
署名单位：
University of California System; University of California Berkeley; University of California System; University of California Berkeley
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.19.1.24
发表日期：
1994
页码：
24-37
关键词：
摘要：
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.
来源URL：