All pairs shortest path in quadratic time with high probability

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices with edge weights chosen independently and uniformly at random from [0,1] is O(n2), in expectation and with high probability. This resolves a long standing open problem.

Joint work with Y. Peres, D. Sotnikov and U. Zwick

Speaker Details

Benny Sudakov received his Ph.D. from Tel Aviv University, had appointments at Princeton University and the Institute for Advanced Studies in Princeton and is currently a Professor of Mathematics in UCLA. His main interests are Combinatorics and its applications in Computer Science.

Date:
Speakers:
Benny Sudakov
Affiliation:
UCLA