PARALLEL ALGORITHMS FOR TERMINAL-PAIR RELIABILITY

This paper reports: 1) parallelization of the two best known sequential algorithms (Dotson & Gobein, and Page & Perry PP-F2TDN) for computing the terminal-pair reliability in a network; 2) Reduce&Partition (R&P), a new sequential algorithm which combines the best efficient features of these two algorithms. On published benchmark networks, R&P runs almost twice as fast as the previously known fastest algorithm. A parallel version of R&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. R&P is both fast and parallelizable. The recursive algorithms require memory O(#vertices 2 #edges), as the recursion depth is limited to (#edges) and at each recursive node a O(#vertices 2) memory is used to represent the network. Thus, the memory requirement of R&P is approximately the same as that of PP-F2TDN and much less than that of the non-recursive Dotson & Gobein algorithm. All 3 algorithms compute exact numerical reliability, but they can easily be modified to produce symbolic reliability expressions. The parallel algorithms were implemented on a shared-memory parallel computer. The R&P approach should be explored to solve other network reliability problem, such as K-terminal reliability. In R&P, the greedy approach was used in selecting shortest paths in order to locally-minimize the number of sub-problems. This selection did not consider the effect of reductions on the subproblems to be generated.