-----------
Tel-Aviv University - Computer Science Colloquium

Sunday, March 26, 14:15-15:15
COFFEE at 14:00

Schreiber Building, Room 309
-----------

Dynamic graph algorithms with applications

Mikkel Thorup

AT&T Labs -- Research

Abstract:

First we review amortized fully-dynamic polylogarithmic algorithms for
connectivity, MST, 2-edge- and biconnecitivity. Second we discuss
how they yield improved static algorithms: connectivity in
constructing a tree from homeomorphic subtrees, MST in maximal tree
packings in graphs, and 2-edge connectivity for finding unique
matchings in graphs.

The application of MST for maximal tree packing is new (joint work
with David Karger) and when boot-strapped, it yields a fully-dynamic
polylogarithmic 2-approximation algorithms for min-cut.

Finally, on the more practical side, we will discuss how output
senstive algorithms for dynamic shortest paths have been applied
successfully in local search algorithms for improving routing on
the internet, roughly doubling the capacity.

-----------

For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html