The <e1>k</e1>-cut problem is to find a partition of an edge weighted graph into <e1>k</e1> nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for arbitrary <e1>k</e1> and its version involving fixing a vertex in each component is NP hard even for <e1>k</e1>=3. A polynomial algorithm for the case of a fixed <e1>k</e1> is presented
%0 Conference Paper
%1 21960
%A Goldschmidt, O.
%A Hochbaum, D.S.
%B Foundations of Computer Science, 1988., 29th Annual Symposium on
%D 1988
%K min-cut
%P 444-451
%R 10.1109/SFCS.1988.21960
%T Polynomial algorithm for the <e1>k</e1>-cut problem
%X The <e1>k</e1>-cut problem is to find a partition of an edge weighted graph into <e1>k</e1> nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for arbitrary <e1>k</e1> and its version involving fixing a vertex in each component is NP hard even for <e1>k</e1>=3. A polynomial algorithm for the case of a fixed <e1>k</e1> is presented
@inproceedings{21960,
abstract = {The <e1>k</e1>-cut problem is to find a partition of an edge weighted graph into <e1>k</e1> nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for arbitrary <e1>k</e1> and its version involving fixing a vertex in each component is NP hard even for <e1>k</e1>=3. A polynomial algorithm for the case of a fixed <e1>k</e1> is presented},
added-at = {2013-11-02T23:54:09.000+0100},
author = {Goldschmidt, O. and Hochbaum, D.S.},
biburl = {https://www.bibsonomy.org/bibtex/244fb667cbac4a7d8936fb9616c4e0841/ytyoun},
booktitle = {Foundations of Computer Science, 1988., 29th Annual Symposium on},
doi = {10.1109/SFCS.1988.21960},
interhash = {eb771524299f0e68a38e2078b8ead1a6},
intrahash = {44fb667cbac4a7d8936fb9616c4e0841},
keywords = {min-cut},
pages = {444-451},
timestamp = {2013-11-02T23:54:09.000+0100},
title = {Polynomial algorithm for the <e1>k</e1>-cut problem},
year = 1988
}