𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Greedy splitting algorithms for approximating multiway partition problems

✍ Scribed by Liang Zhao; Hiroshi Nagamochi; Toshihide Ibaraki

Publisher
Springer-Verlag
Year
2004
Tongue
English
Weight
187 KB
Volume
102
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An Improved Approximation Algorithm for
An Improved Approximation Algorithm for MULTIWAY CUT
✍ Gruia CΔƒlinescu; Howard Karloff; Yuval Rabani πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 132 KB

Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due