𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the generalized multiway cut in trees problem

✍ Scribed by Hong Liu, Peng Zhang

Book ID
120694224
Publisher
Springer US
Year
2012
Tongue
English
Weight
251 KB
Volume
27
Category
Article
ISSN
1382-6905

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On weighted multiway cuts in trees
On weighted multiway cuts in trees
✍ PΓ©ter L. ErdΕ‘s; LΓ‘szlΓ³ A. SzΓ©kely πŸ“‚ Article πŸ“… 1994 πŸ› Springer-Verlag 🌐 English βš– 751 KB
Minimum multiway cuts in trees
Minimum multiway cuts in trees
✍ PΓ©ter L. ErdΕ‘s; AndrΓ‘s Frank; LΓ‘szlΓ³ SzΓ©kely πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 667 KB

We compare three lower bounds for the minimum cardinality of a multiway cut in a graph separating a given set S of terminals. The main result is a relatively short algorithmic proof for a simplified version of a min-max theorem of the first and the third authors asserting that the best of the three

The multi-multiway cut problem
The multi-multiway cut problem
✍ Adi Avidor; Michael Langberg πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 248 KB
A Simple Algorithm for the Planar Multiw
A Simple Algorithm for the Planar Multiway Cut Problem
✍ Wei-Chang Yeh πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 95 KB

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 tota