✦ LIBER ✦

A 2-Approximation Algorithm for the Directed Multiway Cut Problem

✍ Scribed by Naor, Joseph (Seffi); Zosin, Leonid

Book ID: 118180450
Publisher: Society for Industrial and Applied Mathematics
Year: 2001
Tongue: English
Weight: 113 KB
Volume: 31
Category: Article
ISSN: 0097-5397
DOI: 10.1137/s009753979732147x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

An Approximation Algorithm for the Direc

An Approximation Algorithm for the Directed Telephone Multicast Problem

✍ Michael Elkin; Guy Kortsarz 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 204 KB

A 2-approximation algorithm for the netw

A 2-approximation algorithm for the network substitution problem

✍ Nicolai N. Pisaruk 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 129 KB

A 2 +ɛapproximation algorithm for thek-M

A 2 +ɛapproximation algorithm for thek-MST problem

✍ Sanjeev Arora; George Karakostas 📂 Article 📅 2005 🏛 Springer-Verlag 🌐 English ⚖ 177 KB

A ( °/2) -approximation algorithm for th

A ( °/2) -approximation algorithm for the maximum independent set problem

✍ V.Th. Paschos 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 221 KB

A 3/2-Approximation Algorithm for the Mi

A 3/2-Approximation Algorithm for the Mixed Postman Problem

✍ Raghavachari, Balaji; Veerasamy, Jeyakesavan 📂 Article 📅 1999 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 269 KB