An optimal algorithm for tree geometrical k-cut problem
Sang-Young Cho, Hee‐Chul Kim · International Conference on Mathematical and Computational Methods in Science and Engineering · 2008
Geometrical k-cut problem has numerous applications, particularly in clustering-related setups such as task assignment and VLSI cell placement. This problem is NP-hard in general. We propose an optimal algorithm to solve the problem for tree topology graphs in polynomial time. The time complexity of the algorithm is O(kn3), where n is the number of nodes in a k-terminal graph, with the Goldberg-Tarjan's network flow algorithm.