An efficient parallel strategy for computing K-terminal reliability and finding most vital edges in 2-trees and partial 2-trees

In this paper, we first develop a parallel algorithm for computing K-terminal reliability, denoted by R(G(K)), in 2-trees. Based on this result, we can also compute R(G(K)) 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 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 the connected components of a graph with m edges and n vertices in logarithmic lime. (C) 1998 Academic Press.