%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 }