TY - JOUR
T1 - Improved processor bounds for parallel algorithms for weighted directed graphs
AU - Amato, Nancy
N1 - Funding Information:
Correspondence to: N. Amato, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 W. Main Street, Urbana, IL 61801, USA. * This work was supported in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under contract NOOO14-90-J-1270.
PY - 1993/3/8
Y1 - 1993/3/8
N2 - 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=\t|V\t|, edge weights are drawn from the set \s{0, 1,..., k\s} 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)=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.
AB - 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=\t|V\t|, edge weights are drawn from the set \s{0, 1,..., k\s} 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)=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.
KW - Weighted directed graph
KW - matrix multiplication
KW - parallel algorithms
KW - single-source shortest paths
UR - http://www.scopus.com/inward/record.url?scp=0027911747&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027911747&partnerID=8YFLogxK
U2 - 10.1016/0020-0190(93)90017-4
DO - 10.1016/0020-0190(93)90017-4
M3 - Article
AN - SCOPUS:0027911747
SN - 0020-0190
VL - 45
SP - 147
EP - 152
JO - Information Processing Letters
JF - Information Processing Letters
IS - 3
ER -