PARALLEL ALGORITHM FOR SHORTEST PAIRS OF EDGE-DISJOINT PATHS

Let G = (V, E) be a directed graph having a nonnegative cost associate d with each edge. Let s is an element of V be a special vertex called the source and W subset of V be a set of other vertices called sinks i n G. In this paper, a parallel algorithm is proposed for finding a pai r of edge-disjoint paths from s to each possible sink t is an element of W such that the sum of the costs of the two paths is minimized. Thi s algorithm has processor and time complexities same as those needed t o find shortest paths from s to all sinks t is an element of W, i.e., n(3)/log n processors and O(log(2) n) time. (C) 1996 Academic Press, I nc.