#### Title

Parallel Algorithms For Terminal-Pair Reliability

#### Title - Alternative

J. Supercomput.

#### Keywords

TERMINAL-PAIR RELIABILITY; DIRECTED NETWORK; NETWORK REDUCTION; FACTORING; PARTITIONING; PARALLEL ALGORITHM; SPEED-UP; GRAPH; DIGRAPH; PARALLEL PROCESSING; NETWORK RELIABILITY; FACTORING THEOREM; RECURSIVE ALGORITHM; PROBABILITY; GRAPH; CUTS; Computer Science, Hardware & Architecture; Computer Science, Software; Engineering; Engineering, Electrical & Electronic

#### Abstract

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.

#### Publication Title

Journal of Supercomputing

#### Volume

6

#### Issue/Number

2

#### Publication Date

1-1-1992

#### Document Type

Article

#### DOI Link

#### Language

English

#### First Page

201

#### Last Page

209

#### WOS Identifier

WOS:A1992JR00500004

#### ISSN

0018-9529

#### Recommended Citation

Deo, N, "Parallel Algorithms For Terminal-Pair Reliability" (1992). *Faculty Bibliography*. 2036.

http://stars.library.ucf.edu/facultybib/2036