Improved processor bounds for parallel algorithms for weighted directed graphs uri icon

abstract

  • We present a parallel algorithm that solves the single-source shortest path problem (SSSP) for a weighted digraph G=(V, E) in time O(log2n) 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 nn integer matrices over a ring in O(log n) time (currently, M(n)=n2.376 ). This algorithm is a generalization of the O(log2n) 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 (n3) (within a polylog factor) without increasing the running time. 1993.

published proceedings

  • Information Processing Letters

author list (cited authors)

  • Amato, N.

citation count

  • 7

complete list of authors

  • Amato, Nancy

publication date

  • March 1993