**An Efficient Parallel Algorithm for the All Pairs
Shortest Path Problem using Processor Arrays with Reconfigurable Bus Systems
**

*Technical Report B-13-99*

July 29, 1999

Rajeev Wankar

Elfriede Fehr

N.S.Chaudhari*

Freie UniversitŠät Berlin, Institut fźür Informatik

wankar@inf.fu-berlin.de

fehr@inf.fu-berlin.de

*** School of Computer Science, DAVV Indore, India**

**Abstract**

The all pairs shortest path problem is a class of the algebraic path problem.
Many parallel algorithms for the solution of this problem appear in the
literature. One of the efficient parallel algorithms on W-RAM model is
given by Kucera. Though efficient, algorithms written for the W-RAM model
of parallel computation are too idealistic to be implemented on the current
hardware. In this report we present an efficient parallel algorithm for
the solution of this problem using a relatively new model of parallel computing,
Processor Arrays with Reconfigurable Bus Systems. The parallel time complexity
of this algorithm is O(log_{2} n) and processors complexity is
n^{2} x n x n.

`Get the report in postscript
or in PDF
format here`

Server: fubinf.inf.fu-berlin.de

File: pub/reports/tr-b-99-13.ps.gz