[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

On the Exponent of the All Pairs Shortest Path Problem

Published: 01 April 1997 Publication History

Abstract

The upper bound on the exponent, of matrix multiplication over a ring that was three in 1968 has decreased several times and since 1986 it has been 2.376. On the other hand, the exponent of the algorithms known for the all pairs shortest path problem has stayed at three all these years even for the very special case of directed graphs with uniform edge lengths. In this paper we give an algorithm of timeO(n log3n), =(3+ )/2, for the case of edge lengths in { 1, 0, 1}. Thus, for the current known bound on, we get a bound on the exponent, <2.688. In case of integer edge lengths with absolute value bounded above byM, the time bound isO((Mn) log3n) and the exponent is less than 3 forM=O(n ), for <0.116 and the current bound on .

References

[1]
A.V. Aho, J. Hopcroft, J.B. Ullman, Addison¿Wesley, Reading, 1974.
[2]
K.K. Ahuja, K. Mehlhorn, J.B. Orlin, R.E. Tarjan, Faster algorithms for the shortest path problem, J. Assoc. Comput. Mach., 37 (1990) 213-223.
[3]
N. Alon, Z. Galil, O. Margalit, M. Naor, On witnesses for Boolean matrix multiplications and for shortest paths
[4]
D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9 (1990) 251-280.
[5]
E.W. Dijkstra, A note on two problems in connection with graphs, Numer. Math., 1 (1959) 269-271.
[6]
M.L. Fredman, New bounds on the complexity of the shortest path problem, SIAM J. Comput., 5 (1976) 83-89.
[7]
H. N. Gabow, Scaling algorithms for network problems, Proceedings 24th Annual Symp. on Foundation of Comput. Sci, 1983
[8]
L. R. Kerr, 1970, Cornell University
[9]
S.C. Kleene, Representation of events in nerve nets and finite automata, Princeton Univ. Press, Princeton, 1956.
[10]
D. Krager, 1992
[11]
O. Margalit, Tel Aviv University
[12]
R. Seidel, On the all-pairs-shortest-path problem, Proceedings, 24th ACM Annual Symp. on Theory of Computing, 1992
[13]
V. Strassen, Gaussian elimination is not optimal, Numer. Math., 13 (1969) 354-356.
[14]
G. Yuval, An algorithm for finding all shortest paths usingN2.81, Inform. Process. Lett., 4 (1976) 155-156.

Cited By

View all
  • (2024)An Improved Algorithm for The k-Dyck Edit Distance ProblemACM Transactions on Algorithms10.1145/362753920:3(1-25)Online publication date: 21-Jun-2024
  • (2024)Shortest distances as enumeration problemDiscrete Applied Mathematics10.1016/j.dam.2023.08.027342:C(89-103)Online publication date: 15-Jan-2024
  • (2023)The Fine-Grained Complexity of CFL ReachabilityProceedings of the ACM on Programming Languages10.1145/35712527:POPL(1713-1739)Online publication date: 11-Jan-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences
Journal of Computer and System Sciences  Volume 54, Issue 2
Special issue: papers from the 32nd and 34th annual symposia on foundations of computer science, Oct. 2–4, 1991 and Nov. 3–5, 1993
April 1997
166 pages
ISSN:0022-0000
Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 April 1997

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)An Improved Algorithm for The k-Dyck Edit Distance ProblemACM Transactions on Algorithms10.1145/362753920:3(1-25)Online publication date: 21-Jun-2024
  • (2024)Shortest distances as enumeration problemDiscrete Applied Mathematics10.1016/j.dam.2023.08.027342:C(89-103)Online publication date: 15-Jan-2024
  • (2023)The Fine-Grained Complexity of CFL ReachabilityProceedings of the ACM on Programming Languages10.1145/35712527:POPL(1713-1739)Online publication date: 11-Jan-2023
  • (2023)Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and MoreProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585237(419-432)Online publication date: 2-Jun-2023
  • (2023) Matrix and Vector Products for Inputs Decomposable into Few Monotone SubsequencesComputing and Combinatorics10.1007/978-3-031-49193-1_5(55-68)Online publication date: 15-Dec-2023
  • (2022)Undirected (1+𝜀)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithmsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520074(478-487)Online publication date: 9-Jun-2022
  • (2022)Faster min-plus product for monotone instancesProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520057(1529-1542)Online publication date: 9-Jun-2022
  • (2022)The FastMap Pipeline for Facility Location ProblemsPRIMA 2022: Principles and Practice of Multi-Agent Systems10.1007/978-3-031-21203-1_25(417-434)Online publication date: 16-Nov-2022
  • (2021)All-pairs LCA in DAGsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458082(273-289)Online publication date: 10-Jan-2021
  • (2021)Approximation Algorithms for Large Scale Data AnalysisProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458813(30-32)Online publication date: 20-Jun-2021
  • Show More Cited By

View Options

View options

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media