Wf. Liang et al., NC ALGORITHMS FOR DYNAMICALLY SOLVING THE ALL PAIRS SHORTEST PATHS PROBLEM AND RELATED PROBLEMS, Information processing letters, 58(3), 1996, pp. 149-155
Citations number
14
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
We consider the problem of dynamically maintaining a solution of all p
airs shortest paths in a directed weighted graph G = (V, E) undergoing
a sequence of edge insertions and/or the edge cost decreases, and pre
sent a simple data structure to support the above operations, The prop
osed algorithm for maintaining the data structure requires O(log n) ti
me and O(n(2)) processors for each of the operations above. Furthermor
e, our algorithm is able to answer n(2) queries concerning the lengths
of all pairs shortest paths in O(1) time, and to find n shortest path
s in O(log n) time. The same bounds for similar operations can be achi
eved for other problems such as dynamically maintaining all pairs long
est 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 o
ur knowledge, no partially dynamic NC algorithm using O(n(2)) processo
rs for these problems is known yet, despite the existence of several e
fficient sequential algorithms, All known NC algorithms for these prob
lems are based on matrix multiplication which requires M(n) processors
at least. Currently the best result for M(n) is n(2.376) (Coppersmith
and Winograd, 1987). Unless otherwise specified, our computational mo
del 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.