TY - JOUR

T1 - Efficient parallel strategy for computing K-terminal reliability and finding most vital edge in 2-trees and partial 2-trees

AU - Ho, Chin Wen

AU - Hsieh, Sun Yuan

AU - Chen, Gen Huey

PY - 1997/1/1

Y1 - 1997/1/1

N2 - We develop a parallel strategy to compute K-terminal reliability in 2-trees and partial 2-trees. We also solve the problem of finding the most vital edge with respect to K-terminal reliability in partial 2-trees. Our algorithms take O(log n) time with C(m, n) processors on a CRCW PRAM, where C(m, n) is the number of processors required to find connected components of a graph with m edges and n vertices in logarithmic time.

AB - We develop a parallel strategy to compute K-terminal reliability in 2-trees and partial 2-trees. We also solve the problem of finding the most vital edge with respect to K-terminal reliability in partial 2-trees. Our algorithms take O(log n) time with C(m, n) processors on a CRCW PRAM, where C(m, n) is the number of processors required to find connected components of a graph with m edges and n vertices in logarithmic time.

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

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

M3 - Conference article

AN - SCOPUS:0030646763

SP - 603

EP - 607

JO - Proceedings of the International Parallel Processing Symposium, IPPS

JF - Proceedings of the International Parallel Processing Symposium, IPPS

SN - 1063-7133

T2 - Proceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97

Y2 - 1 April 1997 through 5 April 1997

ER -