All Pairs Shortest Path in Quadratic Time with High Probability

Speaker  Benjamin Sudakov

Host  Madhu Sudan/Adam Kalai

Duration  01:14:27

Date recorded  27 April 2011

All-pairs shortest path problem is one of the most important, and most studied algorithmic graph problems. For this problem many researches develop algorithms which work well on random instances, most notably complete directed graphs on n vertices with random weights on their edges. The simplest such model, on which we focus in this talk, is the one in which all edge weights are drawn independently at random from the uniform distribution on [0,1]

We present an all-pairs shortest path algorithm in this setting whose running time is O(n2), in expectation and with high probability. This is clearly best possible and resolves a long standing open problem.

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

©2011 Microsoft Corporation. All rights reserved.
> All Pairs Shortest Path in Quadratic Time with High Probability