Title

Parallel Algorithms For Terminal-Pair Reliability

Keywords

Digraph; Directed network; Factoring; Graph; Network reduction; Parallel algorithm; Parallel processing; Partitioning; Speedup; Terminal-pair reliability

Abstract

This paper reports: 1) parallelization of the two best known sequential algorithms (Dotson & Gobein, and Page & Perry PP-F2TDN) for computing the terminalpair reliability in a network; 2) ReduceLkPartition (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*- #edges), as the recursion depth is limited to (#edges) and at each recursive node a O(#vertices2) memory is used to represent the network. Thus, the memory requirement of R&P is approximately the same as that of PP-mTDN and much less than that of the non-recursive Dotson & Gobein algorithm. AU 3 algorithms compute exact numerical reliability, but they can easily be modified to produce symbolic reliability expressions. The parallel algorithms were implemented on a sharedmemory 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 subproblems. This selection did not consider the effect of reductions on the subproblems to be generated. © 1992 IEEE

Publication Date

1-1-1992

Publication Title

IEEE Transactions on Reliability

Volume

41

Issue

2

Number of Pages

201-209

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/24.257782

Socpus ID

0026882380 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0026882380

This document is currently not available here.

Share

COinS