An Optimal Algorithm for General Array Geometrical k-cut Problem

摘要

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 general array topology graphs in polynomial time. The time complexity of the algorithm is O(kn~3), where n is the number of nodes in a k-terminal graph, with the Goldberg-Tarjan's network flow algorithm.