Title :
An efficient parallel strategy for computing K-terminal reliability and finding most vital edge in 2-trees and partial 2-trees
Author :
Ho, Chin-Wen ; Hsieh, Sun-Yuan ; Chen, Gen-Huey
Author_Institution :
Dept. of Comput. Sci., Nat. Central Univ., Chung-Li, Taiwan
Abstract :
The authors develop a parallel strategy to compute K-terminal reliability in 2-trees and partial 2-trees. They also solve the problem of finding the most vital edge with respect to K-terminal reliability in partial 2-trees. The 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
Keywords :
computational complexity; parallel algorithms; reliability; trees (mathematics); 2-trees; CRCW PRAM; K-terminal reliability computation; computation time; connected graph components; edges; efficient parallel strategy; logarithmic time; most vital edge finding; partial 2-trees; processors; vertices; Computer network reliability; Computer networks; Computer science; Concurrent computing; Electronic mail; NP-hard problem; Phase change random access memory; Reliability engineering; Telecommunication network reliability; Tree graphs;
Conference_Titel :
Parallel Processing Symposium, 1997. Proceedings., 11th International
Conference_Location :
Genva
Print_ISBN :
0-8186-7793-7
DOI :
10.1109/IPPS.1997.580963
