On the exponent of the all pairs shortest path problem

Noga Alon, Zvi Galil, Oded Margalit

Research output: Chapter in Book/Report/Conference proceedingConference contribution

39 Scopus citations

Abstract

The upper bound on the exponent, ω, of matrix multiplication over a ring, which 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. An algorithm is given of time O(nν log 3 n), ν = (3 + ω)/2, for the case of edge lengths in {-1,0,1}. Thus, for the current known bound on ω, a bound on the exponent, ν < 2.688, is obtained. In case of integer edge lengths with absolute value bounded above by M, the time bound is O((Mn)ν log 3 n) and the exponent is less than 3 for M = O(nα), for α < 0.116 and the current bound on ω.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages569-575
Number of pages7
ISBN (Print)0818624450
StatePublished - Dec 1 1991
EventProceedings of the 32nd Annual Symposium on Foundations of Computer Science - San Juan, PR, USA
Duration: Oct 1 1991Oct 4 1991

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 32nd Annual Symposium on Foundations of Computer Science
CitySan Juan, PR, USA
Period10/1/9110/4/91

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'On the exponent of the all pairs shortest path problem'. Together they form a unique fingerprint.

Cite this