Parallel algorithms for terminal-pair reliability

The parallelization of the two best-known sequential algorithms, that of W.P. Dotson and J.O. Gobein (1979) and that of L.B. Page and J.E. Perry (PP-F2TDN) (1989) for computing the terminal-pair reliability in a network is discussed. Reduce and Partition (R and P), a novel sequential algorithm which combines the best efficient features of these two algorithms, is presented. It is shown that R and P runs almost twice as fast as the previously known fastest algorithm. A parallel version of R and P is also presented. The execution times of all three parallel algorithms with various numbers of processors for different networks on the BBN Butterfly parallel computer are provided. The parallel algorithms were implemented on a shared-memory parallel computer. In R and P, the greedy approach was used in selecting shortest paths in order to locally minimize the number of subproblems. This selection did not consider the effect of reductions on the subproblems to be generated