Improved processor bounds for parallel algorithms for weighted directed graphs | Academic Article individual record

We present a parallel algorithm that solves the single-source shortest path problem (SSSP) for a weighted digraph G=(V, E) in time O(log 2 n) using M(n) processors on an exclusive-read exclusive-write parallel random access machine (EREW PRAM), where n= |V |, edge weights are drawn from the set s{0, 1,..., ks} for some constant k, and M(n) is the number of processors necessary to multiply two n×n integer matrices over a ring in O(log n) time (currently, M(n)=n 2.376 ). This algorithm is a generalization of the O(log 2 n) time, M(n) processor EREW PRAM algorithm due to Gazit and Miller for the SSSP problem in an unweighted digraph. We also briefly explain how our solution of the SSSP problem for a weighted digraph can be used to reduce the previous known processor bounds for a number of digraph problems to M(n) from Θ(n 3 ) (within a polylog factor) without increasing the running time. © 1993.

author list (cited authors)
Amato, N.
publication date
published in
citation count