Polynomial algorithm for the k-cut problem
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 444-451
- https://doi.org/10.1109/sfcs.1988.21960
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
This publication has 4 references indexed in Scilit:
- An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut ProblemSIAM Journal on Algebraic Discrete Methods, 1985
- Optimal attack and reinforcement of a networkJournal of the ACM, 1985
- Connectivity and edge-disjoint spanning treesInformation Processing Letters, 1983
- Tough graphs and hamiltonian circuitsDiscrete Mathematics, 1973