All-pairs shortest paths for unweighted undirected graphs in o(mn) time

ABSTRACT

We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times:[EQUATION]These represent the best time bounds known for the problem for all m ≪ n^1.376. We also obtain a similar type of result for the diameter problem for unweighted directed graphs.

REFERENCES

• 1: Ravindra K. Ahuja , Kurt Mehlhorn , James Orlin , Robert E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM (JACM), v.37 n.2, p.213-223, April 1990 [doi>10.1145/77600.77615]
• 2: D. Aingworth , C. Chekuri , P. Indyk , R. Motwani, Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication), SIAM Journal on Computing, v.28 n.4, p.1167-1181, Aug. 1999 [doi>10.1137/S0097539796303421]
• 3: Noga Alon , Zvi Galil , Oded Margalit, On the exponent of the all pairs shortest path problem, Journal of Computer and System Sciences, v.54 n.2, p.255-262, April 1997 [doi>10.1006/jcss.1997.1388]
• 4: V. L. Arlazarov, E. C. Dinic, M. A. Kronrod, and I. A. Faradzev. On economical construction of the transitive closure of a directed graph. Soviet Math. Dokl., 11:1209--1210, 1970.
• 5: T. M. Chan. All-pairs shortest paths with real weights in O(n3/log n) time. In Proc. 9th Workshop Algorithms Data Struct., Lect. Notes Comput. Sci., vol. 3608, Springer-Verlag, pages 318--324, 2005.
• 6: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 7: W. Dobosiewicz. A more efficient algorithm for the min-plus multiplication. Int. J. Computer Math., 32:49--60, 1990.
• 8: Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908]
• 9: Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Journal of Computer and System Sciences, v.51 n.2, p.261-272, Oct. 1995 [doi>10.1006/jcss.1995.1065]
• 10: M. L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput., 5:49--60, 1976.
• 11: Zvi Galil , Oded Margalit, All pairs shortest distances for graphs with small integer length edges, Information and Computation, v.134 n.2, p.103-139, May 1, 1997 [doi>10.1006/inco.1997.2620]
• 12: Zvi Galil , Oded Margalit, All pairs shortest paths for graphs with small integer length edges, Journal of Computer and System Sciences, v.54 n.2, p.243-254, April 1997 [doi>10.1006/jcss.1997.1385]
• 13: Torben Hagerup, Improved Shortest Paths on the Word RAM, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.61-72, July 09-15, 2000
• 14: Yijie Han, Improved algorithm for all pairs shortest paths, Information Processing Letters, v.91 n.5, p.245-250, 15 September 2004 [doi>10.1016/j.ipl.2004.05.006]
• 15: Valerie King, Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.81, October 17-18, 1999
• 16: Seth Pettie, A new approach to all-pairs shortest paths on real-weighted graphs, Theoretical Computer Science, v.312 n.1, p.47-74, 26 January 2004 [doi>10.1016/S0304-3975(03)00402-X]
• 17: Seth Pettie , Vijaya Ramachandran, A Shortest Path Algorithm for Real-Weighted Undirected Graphs, SIAM Journal on Computing, v.34 n.6, p.1398-1431, 2005 [doi>10.1137/S0097539702419650]
• 18: Raimund Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, v.51 n.3, p.400-403, Dec. 1995 [doi>10.1006/jcss.1995.1078]
• 19: Avi Shoshan , Uri Zwick, All Pairs Shortest Paths in Undirected Graphs with Integer Weights, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.605, October 17-18, 1999
• 20: P. M. Spira. A new algorithm for finding all shortest paths in a graph of positive arcs in average time O(n2 log2n). SIAM J. Comput., 2:28--32, 1973.
• 21: V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354--356, 1969.
• 22: Tadao Takaoka, A new upper bound on the complexity of the all pairs shortest path problem, Information Processing Letters, v.43 n.4, p.195-199, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90200-F]
• 23: T. Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica, 20:309--318, 1998.
• 24: T. Takaoka. A faster algorithm for the all-pairs shortest path problem and its application. In Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, Springer-Verlag, pages 278--289, 2004.
• 25: Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
• 26: Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Journal of Computer and System Sciences, v.69 n.3, p.330-353, November 2004 [doi>10.1016/j.jcss.2004.04.003]
• 27: Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]
• 28: R. Yuster and U. Zwick. Fast sparse matrix multiplication. In Proc. 12th European Sympos. Algorithms, Lect. Notes Comput. Sci., vol. 3221, Springer-Verlag, pages 604--615, 2004.
• 29: All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]
• 30: U. Zwick. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. In Proc. 15th Int. Sympos. Algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, Springer-Verlag, pages 921--932, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory