✦ LIBER ✦

The multi-multiway cut problem

✍ Scribed by Adi Avidor; Michael Langberg

Book ID: 108281297
Publisher: Elsevier Science
Year: 2007
Tongue: English
Weight: 248 KB
Volume: 377
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2007.02.026

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Generalizedk-multiway cut problems

✍ Jiping Liu; Yuejian Peng; Cheng Zhao 📂 Article 📅 2006 🏛 Springer-Verlag 🌐 English ⚖ 244 KB

On the generalized multiway cut in trees

On the generalized multiway cut in trees problem

✍ Hong Liu, Peng Zhang 📂 Article 📅 2012 🏛 Springer US 🌐 English ⚖ 251 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

A 2-Approximation Algorithm for the Dire

A 2-Approximation Algorithm for the Directed Multiway Cut Problem

✍ Naor, Joseph (Seffi); Zosin, Leonid 📂 Article 📅 2001 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 113 KB

Approximation Algorithms || Multiway Cut

Approximation Algorithms || Multiway Cut and k-Cut

✍ Vazirani, Vijay V. 📂 Article 📅 2003 🏛 Springer Berlin Heidelberg 🌐 English ⚖ 853 KB

Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872-1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed con jecture that P -=/= NP, their

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