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

Authors
GOLDSCHMIDT O HOCHBAUM DS
Citation
O. Goldschmidt et Ds. Hochbaum, A POLYNOMIAL ALGORITHM FOR THE KAPPA-CUT PROBLEM FOR FIXED KAPPA, Mathematics of operations research, 19(1), 1994, pp. 24-37
Citations number
16
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
Journal title
Mathematics of operations research → ACNP
ISSN journal
0364765X
Volume
19
Issue
1
Year of publication
1994
Pages
24 - 37
Database
ISI
SICI code
0364-765X(1994)19:1<24:APAFTK>2.0.ZU;2-3
Abstract
The k-cut problem is to find a partition of an edge weighted graph int o k nonempty components, such that the total edge weight between compo nents is minimum. This problem is NP-complete for an arbitrary k and i ts 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 i n O(n(k2/2-3k/2+4)T(n, m)) steps, where T(n, m) is the running time re quired to find the minimum (s, t)-cut on a graph with n vertices and m edges.