All-Pairs Shortest Paths in $O(n^2)$ time with high probability

Details All-Pairs Shortest Paths in $O(n^2)$ time with high probability All-Pairs Shortest Paths in $O(n^2)$ time with high probability

2011-05-19

arxiv.org/abs/1105.3770v1

Mathematics

Combinatorics

Scientific paper

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on $n$ vertices whose edge weights are 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. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of \emph{locally shortest paths} in such randomly weighted graphs is $O(n^2)$, in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in $O(\log^{2}n)$ expected time.

Affiliated with

Also associated with

No associations

Rating

All-Pairs Shortest Paths in $O(n^2)$ time with high probability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with All-Pairs Shortest Paths in $O(n^2)$ time with high probability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and All-Pairs Shortest Paths in $O(n^2)$ time with high probability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-68622