TY - JOUR

T1 - An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees

AU - Ho, Chin Wen

AU - Hsieh, Sun Yuan

AU - Chen, Gen Huey

N1 - Funding Information:
1This work was partially supported by the National Science Council of Taiwan under Grant NSC84-2213-E-008-005. We thank the anonymous referees for helping us improve the presentation of this paper. 2Corresponding author. Address: Department of Computer Science and Information Engineering, National Central University, Chung-Li, Taiwan 32054. E-mail: hocw csie.ncu.edu.tw.

PY - 1998/6/15

Y1 - 1998/6/15

N2 - In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(GK), in 2-trees. Based on this result, we can also computeR(GK) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(logn) time withC(m,n) processors on a CRCW PRAM, whereC(m,n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.

AB - In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(GK), in 2-trees. Based on this result, we can also computeR(GK) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(logn) time withC(m,n) processors on a CRCW PRAM, whereC(m,n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.

KW - Network reliability,K-terminal reliability, partial 2-tree, 2-tree, most vital edge

UR - http://www.scopus.com/inward/record.url?scp=0038900397&partnerID=8YFLogxK

U2 - 10.1006/jpdc.1998.1454

DO - 10.1006/jpdc.1998.1454

M3 - 期刊論文

AN - SCOPUS:0038900397

VL - 51

SP - 89

EP - 113

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 2

ER -