Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
All pairs shortest path in quadratic time with high probability

Speaker  Benny Sudakov

Affiliation  UCLA

Host  Yuval Peres

Duration  01:00:39

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.
> All pairs shortest path in quadratic time with high probability