#### Title

Parallel Algorithms For Terminal-Pair Reliability

#### Abbreviated Journal Title

IEEE Trans. Reliab.

#### 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.

#### Journal Title

Ieee Transactions on Reliability

#### Volume

41

#### Issue/Number

2

#### Publication Date

1-1-1992

#### Document Type

Article

#### DOI Link

#### Language

English

#### First Page

201

#### Last Page

209

#### WOS Identifier

#### ISSN

0018-9529

#### Recommended Citation

"Parallel Algorithms For Terminal-Pair Reliability" (1992). *Faculty Bibliography 1990s*. 439.

https://stars.library.ucf.edu/facultybib1990/439

## Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu