An expected-case sub-cubic solution to the all-pairs shortest path problem in R

Details An expected-case sub-cubic solution to the all-pairs shortest path problem in R An expected-case sub-cubic solution to the all-pairs shortest path problem in R

2009-12-05

arxiv.org/abs/0912.0975v1

Computer Science

Data Structures and Algorithms

9 pages, 5 figures

Scientific paper

It has been shown by Alon et al. that the so-called 'all-pairs shortest-path' problem can be solved in O((MV)^2.688 * log^3(V)) for graphs with V vertices, with integer distances bounded by M. We solve the more general problem for graphs in R (assuming no negative cycles), with expected-case running time O(V^2.5 * log(V)). While our result appears to violate the Omega(V^3) requirement of "Funny Matrix Multiplication" (due to Kerr), we find that it has a sub-cubic expected time solution subject to reasonable conditions on the data distribution. The expected time solution arises when certain sub-problems are uncorrelated, though we can do better/worse than the expected-case under positive/negative correlation (respectively). Whether we observe positive/negative correlation depends on the statistics of the graph in question. In practice, our algorithm is significantly faster than Floyd-Warshall, even for dense graphs.

Affiliated with

Also associated with

No associations

Rating

An expected-case sub-cubic solution to the all-pairs shortest path problem in R 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 An expected-case sub-cubic solution to the all-pairs shortest path problem in R, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An expected-case sub-cubic solution to the all-pairs shortest path problem in R will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-706383