Duration: 1:01:03

78 views

1

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