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:
Filename Description Size
Thumbnail2010004140OK.pdf94.58 kB
Adobe PDF
Full metadata record
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: