Title :
Polynomial algorithm for the k-cut problem
Author :
Goldschmidt, Olivier ; Hochbaum, Dorit S.
Author_Institution :
California Univ., Berkeley, CA, USA
Abstract :
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 arbitrary k and its version involving fixing a vertex in each component is NP hard even for k=3. A polynomial algorithm for the case of a fixed k is presented
Keywords :
computational complexity; graph theory; NP hard; NP-complete; edge weighted graph; k nonempty components; k-cut problem; partition; polynomial algorithm; total edge weight; vertex; Clustering algorithms; Partitioning algorithms; Polynomials; Tail; Very large scale integration;
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
DOI :
10.1109/SFCS.1988.21960
