A Simple Algorithm For The Planar Multiway Cut Problem

Yeh, W

A Simple Algorithm For The Planar Multiway Cut Problem

Yeh, W

Permalink

Publisher:: Academic Press Inc
Publication Type:: Journal Article
Citation:: Journal Of Algorithms, 2001, 39 (1), pp. 68 - 77
Issue Date:: 2001-01

Closed Access

	Filename	Description	Size
	2010004140OK.pdf		94.58 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Yeh, W	en_US
dc.date.issued	2001-01	en_US
dc.identifier.citation	Journal Of Algorithms, 2001, 39 (1), pp. 68 - 77	en_US
dc.identifier.issn	0196-6774	en_US
dc.identifier.uri	http://hdl.handle.net/10453/15133
dc.description.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 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.	en_US
dc.publisher	Academic Press Inc	en_US
dc.relation.ispartof	Journal Of Algorithms	en_US
dc.relation.isbasedon	10.1006/jagm.2000.1148	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	A Simple Algorithm For The Planar Multiway Cut Problem	en_US
dc.type	Journal Article
utslib.citation.volume	1	en_US
utslib.citation.volume	39	en_US
utslib.location.activity	ISI:000168097000003	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
dc.location.activity	ISI:000168097000003	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Software
pubs.organisational-group	/University of Technology Sydney/Strength - AAI - Advanced Analytics Institute Research Centre
utslib.copyright.status	closed_access
pubs.consider-herdc	false	en_US
pubs.issue	1	en_US
pubs.volume	39	en_US

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 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:

http://hdl.handle.net/10453/15133