TY - JOUR
AB - 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.
AU - Yeh, W
DA - 2001/01/01
DO - 10.1006/jagm.2000.1148
EP - 77
JO - Journal Of Algorithms
PB - Academic Press Inc
PY - 2001/01/01
SP - 68
TI - A Simple Algorithm For The Planar Multiway Cut Problem
VL - 39
Y1 - 2001/01/01
Y2 - 2020/10/28
ER -