A Simple Algorithm For The Planar Multiway Cut Problem
- Academic Press Inc
- Publication Type:
- Journal Article
- Journal Of Algorithms, 2001, 39 (1), pp. 68 - 77
- Issue Date:
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.
Please use this identifier to cite or link to this item: