Title

Parallel Algorithms For Terminal-Pair Reliability

Authors

Authors

N. Deo;M. Medidi

Comments

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

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

Language

English

First Page

201

Last Page

209

WOS Identifier

WOS:A1992HY35900012

ISSN

0018-9529

Share

COinS