A Simple Algorithm For The Planar Multiway Cut Problem

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 devel- oped a very simple algorithm with time complexity Ok 3 .k1 nk.2 k4 2 nk 3 k2 1 k lognk... Our algorithm is based on some simple theorems 2 2 that characterize the structure of the k-way cut. It is also better than the best known algorithm with time complexity O4k k n2 k1 log n. for the planar multiway cut problem