All pairs shortest path in quadratic time with high probability

Опубликовано 17 августа 2016, 21:57

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(n^2)$, in expectation and with high probability. This resolves a long standing open problem. Joint work with Y. Peres, D. Sotnikov and U. Zwick