Abstract
The traditional min-cut problem involves finding a cut with minimum weight between two specified vertices. The planar multiway cut problem is a NP-hard generalization of the min-cut problem. It involves separating a weighted planar graph with k specified vertices into k components such that the total weight between the components is minimized. This problem has important applications in computer science, engineering, and management science. In this study, we developed a very simple algorithm with time complexity O((k - 3/2) k-1 · (n - k) 2k-4 · [nk -3/2k 2 + 1/2k] · log(n -k)). Our algorithm is based on some simple theorems that characterize the structure of the k-way cut. It is also better than the best known algorithm with time complexity O(4k k · n 2k-1 · log n) for the planar multiway cut problem. © 2001 Academic Press.