All pairs shortest path in quadratic time with high probability

Speaker  Benny Sudakov

Host  Yuval Peres

Affiliation  UCLA

Duration  01:00:39

Date recorded  30 July 2010

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

©2010 Microsoft Corporation. All rights reserved.
> All pairs shortest path in quadratic time with high probability