Duration: 1:14:51

105 views

2

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(n^2)$, 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