MADALGO Seminar, Mikkel Thorup, AT&T Labs-Research
2008.08.25 |
| Date | Thu Sep 04 |
| Time | 12:15 — 13:00 |
| Location | Turing-014 |
Title: Efficient Cuts via Greedy Tree Packing
Speaker: Mikkel Thorup, AT&T Labs-Research
Abstract:
We study a simple greedy tree packing of a graph and use it to derive better algorithms for fully-dynamic min-cut and for the static k-way cut problem.
A greedy tree packing is a sequence of spanning tree where each new tree is aminimum spanning tree with respect to the edge loads from the previous trees, that is, the load of an edge is the number of times it has been used by the previous trees.
Aminimum k-way cut is a minimum set of edges whose removal splits the graph in k components. A min-cut is a minimum 2-way cut.
If the (unknown) edge connectivity of the graphis c, we show that if we pack c^7*log^3 m trees, then some min-cut is crossed exactly once by some tree. This leadsto the best fully-dynamic min-cut algorithm (presented at STOC'01) If we pack k^3*log n trees, then every minimum k-way cut is crossed 2k-2 times by some tree. This leads to the best determinstic algorithm for k-way cut (presented at STOC'08)
Host: Lars Arge