✦ LIBER ✦

On the Exponent of the All Pairs Shortest Path Problem

✍ Scribed by Noga Alon; Zvi Galil; Oded Margalit

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 900 KB
Volume: 54
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1997.1388

No coin nor oath required. For personal study only.

✦ Synopsis

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(n & log 3 n), &=(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 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 |.

📜 SIMILAR VOLUMES

On the All-Pairs-Shortest-Path Problem i

On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs

✍ R. Seidel 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 318 KB

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted \(n\)-vertex graphs in time \(O(M(n) \log n)\), where \(M(n)\) denotes the time necessary to multiply two \(n \times n\) matrices of small integers (which is currently kno

On the all-pairs shortest-path algorithm

On the all-pairs shortest-path algorithm of Moffat and Takaoka

✍ Kurt Mehlhorn; Volker Priebe 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 3 views

We review how to solve the all-pairs shortest-path problem in a nonnegatively Ž 2 . weighted digraph with n vertices in expected time O n log n . This bound is shown to hold with high probability for a wide class of probability distributions on nonnegatively weighted Ž . digraphs. We also prove that

The all-pairs quickest path problem

✍ D.T. Lee; E. Papadopoulou 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 625 KB

Solving the all-pair shortest path query

Solving the all-pair shortest path query problem on interval and circular-arc graphs

✍ Chen, Danny Z.; Lee, D. T.; Sridhar, R.; Sekharan, Chandra N. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 3 views

In this paper, we study the following all-pair shortest path query problem: Given the interval model of an unweighted interval graph of n vertices, build a data structure such that each query on the shortest path (or its length) between any pair of vertices of the graph can be processed efficiently

An optimal algorithm to solve the all-pa

An optimal algorithm to solve the all-pair shortest path problem on interval graphs

✍ R. Ravi; Madhav V. Marathe; C. Pandu Rangan 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 646 KB

A simpleO(n2) algorithm for the all-pair

A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph

✍ Mirchandani, Prakash 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 3 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a