All-Pairs Shortest Paths with Real Weights in O(n ³/log n) Time

1. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)

   MATH  Google Scholar 

2. Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. J. Comput. Sys. Sci. 54, 255–262 (1997)

   Article  MATH  MathSciNet  Google Scholar 

3. Arlazarov, V.L., Dinic, E.C., Kronrod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of a directed graph. Soviet Math. Dokl. 11, 1209–1210 (1970)

   MATH  Google Scholar 

4. Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators. In: Proc. 30th ACM Sympos. Theory Comput., pp. 279–288 (1998)

   Google Scholar 

5. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9, 251–280 (1990)

   Article  MATH  MathSciNet  Google Scholar 

6. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. McGraw-Hill, New York (2001)

   MATH  Google Scholar 

7. Dobosiewicz, W.: A more efficient algorithm for the min-plus multiplication. Int. J. Computer Math. 32, 49–60 (1990)

   Article  MATH  Google Scholar 

8. Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proc. 15th ACM-SIAM Sympos. Discrete Algorithms, pp. 788–797 (2004)

   Google Scholar 

9. Feder, T., Motwani, R.: Clique partitions, graph compression and speeding-up algorithms. J. Comput. Sys. Sci. 51, 261–272 (1995)

   Article  MATH  MathSciNet  Google Scholar 

10. Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5, 49–60 (1976)

    Article  MathSciNet  Google Scholar 

11. Galil, Z., Margalit, O.: All pairs shortest paths for graphs with small integer length edges. J. Comput. Sys. Sci. 54, 243–254 (1997)

    Article  MATH  MathSciNet  Google Scholar 

12. Han, Y.: Improved algorithm for all pairs shortest paths. Inform. Process. Lett. 91, 245–250 (2004)

    Article  MathSciNet  Google Scholar 

13. Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theoret. Comput. Sci. 312, 47–74 (2004)

    Article  MATH  MathSciNet  Google Scholar 

14. Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. (to appear)

    Google Scholar 

15. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)

    Google Scholar 

16. Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Sys. Sci. 51, 400–403 (1995)

    Article  MathSciNet  Google Scholar 

17. Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: Proc. 40th IEEE Sympos. Found. Comput. Sci., pp. 605–614 (1999)

    Google Scholar 

18. Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik 13, 354–356 (1969)

    Article  MATH  MathSciNet  Google Scholar 

19. Takaoka, T.: A new upper bound on the complexity of the all pairs shortest path problem. Inform. Process. Lett. 43, 195–199 (1992)

    Article  MATH  MathSciNet  Google Scholar 

20. Takaoka, T.: A faster algorithm for the all-pairs shortest path problem and its application. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol. 3106, pp. 278–289. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

21. Yuster, R., Zwick, U.: Fast sparse matrix multiplication. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 604–615. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

22. Zwick, U.: All-pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 289–317 (2002)

    Article  MathSciNet  Google Scholar 

23. Zwick, U.: A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 921–932. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

Download references