On the Exponent of the All Pairs Shortest Path Problem

Noga Alon, Zvi Galil, Oded Margalit

Research output: Contribution to journalArticle

85 Scopus citations

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 time O(nv log3 n), v = (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, v < 2.688. In case of integer edge lengths with absolute value bounded above by M, the time bound is O((Mn)v log3 n) and the exponent is less than 3 for M = O(nα), for α < 0.116 and the current bound on ω.

Original languageEnglish (US)
Pages (from-to)255-262
Number of pages8
JournalJournal of Computer and System Sciences
Volume54
Issue number2
DOIs
StatePublished - Apr 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

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