𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by R. Seidel

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
318 KB
Volume
51
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 known to be (o\left(n^{2.376}\right)) ). We also address the problem of actually finding a shortest path between each pair of vertices and present a randomized algorithm that matches APD in its simplicity and in its expected running time. C 1995 Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

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

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

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