Raimund Seidel
- 1.N. Alon, Z. Galil, and O. Margalit, On the Exponent of the All Pairs Shortest Path Problem, Proc. 32nd FOCS (1991), 569-575. Google Scholar
Digital Library
- 2.D. Coppersmith and S. Winograd, Matrix Multiplica. tion via Arithmetic Progressions, J. of Symbolic Computation 9 (1990), 251-280. Google ScholarDigital Library
- 3.T. Feder and It. Motwani, Clique Partitions, Graphs Compression and Speeding-up Algorithms, Proc. STOC (1991), 123-133. Google ScholarDigital Library
- 4.M. L. Fredman, New Bounds on the Complezity of the Shortest Path Problem, SIAM J. Comp. 5 (1976), 83- 89.Google ScholarCross Ref
- 5.M. L. Fredman and 1t. E. Tarjan, Fibonacci Heaps and thier Uses in Improved Network Optimization AI. gorithms, JACM (1987), 596-615. Google ScholarDigital Library
- 6.D. B. Johnson, Efficient Algorithms }or Shortest Paths in Sparse Networks, JACM (1977), 1-13. Google ScholarDigital Library
- 7.Z. Galil, Private Communication.Google Scholar
- 8.Z. Galil and O. Margalit, On the Exponent of the All Pairs Shortest Path Problem, Manuscript, April 1991.Google Scholar
- 9.H. N. Gabow, Scaling Algorithms ator Network Problems, J. Comput. System Sci. 31 (1985), 148-168. Google ScholarDigital Library
- 10.D. R. Karger, Private Communication.Google Scholar
- 11.D. R. Karger, D. Koller, and S. J. Phillips, Finding the Hidden Path: Time Bounds lor All-Pairs Shortest Paths, Proc. 32nd FOCS (1991), 560-568. Google ScholarDigital Library
- 12.C. C. McGeoch, Finding Shortest Paths with the Optimal Subgraph, Manuscript, 1992.Google Scholar
- 13.V. Pan, How to Multiply Matrices Faster, Springer Lecture Notes in Computer Science 179 (1984). Google ScholarDigital Library
- 14.F. Romani, Shortest-Path Problem is not Harder than Matrix Multiplication, IPL 11 (1980) 134-136.Google ScholarCross Ref
- 15.G. Yuval, An Algorithm for Finding All Shortest Paths Using NTM Infinite-Precision Multiplications, IPL 4 (1976) 155-156.Google ScholarCross Ref
Index Terms
- On the all-pairs-shortest-path problem
Recommendations
A Multiple Pairs Shortest Path Algorithm
The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest ...
Solving all-pairs shortest path by single-source computations
Given an arbitrary directed graph G=(V,E) with non-negative edge lengths, we present an algorithm that computes all pairs shortest paths in time O(mn+mlgn+nT(m,n)), where m is the number of different edges contained in shortest paths and T(m,n) is the ...
Shortest path problem with uncertain arc lengths
Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, ...
Reviews
Noga Alon
An ingenious simple trick enables the author to improve a previous result of myself, Z. Galil, and O. Margalit [1] for an interesting special case. He obtains an algorithm that finds the distances between all pairs of vertices of an n -vertex undirected and unweighted graph in time O M n log n , where M n is the time needed to multiply two n -by- n matrices of small integers (which is known to be O n 2.376 ). This is a beautiful short note. A more general (but more complicated) algorithm that works for the case of small weights as well has been found by Galil and Margalit.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments