Speaker Benny Sudakov
Host Yuval Peres
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.