TY - JOUR

T1 - NC algorithms for dynamically solving the all pairs shortest paths problem and related problems

AU - Liang, Weifa

AU - McKay, Brendan D.

AU - Shen, Hong

PY - 1996/5/13

Y1 - 1996/5/13

N2 - We consider the problem of dynamically maintaining a solution of all pairs shortest paths in a directed weighted graph G= (V, E) undergoing a sequence of edge insertions and/or the edge cost decreases, and present a simple data structure to support the above operations. The proposed algorithm for maintaining the data structure requires O(logn) time and O(n2) processors for each of the operations above. Furthermore, our algorithm is able to answer n2 queries concerning the lengths of all pairs shortest paths in O(1) time, and to find n shortest paths in O(logn) time. The same bounds for similar operations can be achieved for other problems such as dynamically maintaining all pairs longest paths in a directed acyclic graph (DAG), the topological order of a DAG, and the transitive closure of a directed graph. To the best of our knowledge, no partially dynamic NC algorithm using O(n2) processors for these problems is known yet, despite the existence of several efficient sequential algorithms. All known NC algorithms for these problems are based on matrix multiplication which requires M(n) processors at least. Currently the best result for M(n) is n2.376 (Coppersmith and Winograd, 1987). Unless otherwise specified, our computational model is a CREW PRAM in which concurrent read to the same memory cell is allowed, but concurrent write to the same memory cell is forbidden.

AB - We consider the problem of dynamically maintaining a solution of all pairs shortest paths in a directed weighted graph G= (V, E) undergoing a sequence of edge insertions and/or the edge cost decreases, and present a simple data structure to support the above operations. The proposed algorithm for maintaining the data structure requires O(logn) time and O(n2) processors for each of the operations above. Furthermore, our algorithm is able to answer n2 queries concerning the lengths of all pairs shortest paths in O(1) time, and to find n shortest paths in O(logn) time. The same bounds for similar operations can be achieved for other problems such as dynamically maintaining all pairs longest paths in a directed acyclic graph (DAG), the topological order of a DAG, and the transitive closure of a directed graph. To the best of our knowledge, no partially dynamic NC algorithm using O(n2) processors for these problems is known yet, despite the existence of several efficient sequential algorithms. All known NC algorithms for these problems are based on matrix multiplication which requires M(n) processors at least. Currently the best result for M(n) is n2.376 (Coppersmith and Winograd, 1987). Unless otherwise specified, our computational model is a CREW PRAM in which concurrent read to the same memory cell is allowed, but concurrent write to the same memory cell is forbidden.

KW - Parallel algorithms

KW - Partially dynamic graph algorithms

KW - The all pairs shortest paths problem

KW - The longest path problem

KW - The transitive closure problem

KW - Topological sorting

UR - http://www.scopus.com/inward/record.url?scp=30244553898&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(96)00037-3

DO - 10.1016/0020-0190(96)00037-3

M3 - Article

AN - SCOPUS:30244553898

SN - 0020-0190

VL - 58

SP - 149

EP - 155

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -