S. Banerjee et al., PARALLEL ALGORITHM FOR SHORTEST PAIRS OF EDGE-DISJOINT PATHS, Journal of parallel and distributed computing, 33(2), 1996, pp. 165-171
Citations number
11
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
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.