Speaker: Uri Zwick Tel Aviv University
Time: 2004-12-23 14:30-2004-12-23 15:30
Venue: FIT-1-222

Abstract:

Four recent algorithms for various versions of the celebrated All-Pairs Shortest Paths problem will be presented. These algorithms are:
1) A decision tree of depth O(n^{2.5}) for the problem obtained by Fredman (1976), and an explicit O(n^3 (loglog n)^{1/2} / log n) algorithm obtained recently using it.
2) An O(n^{2.575}) algorithm for unweighted directed graphs obtained using fast algebraic matrix multiplication algorithms.
3) A combinatorial O(m^{1/2}n^{3/2}) time algorithm for unweighted undirected graphs which returns distances with additive errors of at most 2. (Joint result with Dor and Halperin)
4) Construction of "approximate distance oracles" for weighted undirected graphs. The construction of such oracles requires only O(mn^{1/2}) time and only O(n^{3/2}) space. A stretch 3 approximation of any distance can be returned in O(1) time. (Joint result with Thorup.)
 

Short Bio: