Journal
SIAM JOURNAL ON COMPUTING
Volume 39, Issue 5, Pages 2075-2089Publisher
SIAM PUBLICATIONS
DOI: 10.1137/08071990X
Keywords
shortest paths; graph algorithms; computational geometry; matrix multiplication
Funding
- NSERC
Ask authors/readers for more resources
In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n(3) log(3) log n/log(2) n), which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of geometrically weighted graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n(3-(3-omega)/(2d+ 4))), where omega < 2.376; in two dimensions, this is O(n(2.922)). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n(3-(3-omega)/ 4)) = O(n(2.844)) time) for APSP in real-vertex-weighted graphs, as well as an improved result (near O(n((3+omega)/2)) = O(n(2.688)) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available