An Efficient Parallel Strategy for Computing K-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees.
Journal
J. Parallel Distrib. Comput.
Journal Volume
51
Journal Issue
2
Pages
89-113
Date Issued
1998
Author(s)
Abstract
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. © 1998 Academic Press.
Subjects
Network reliability,K-terminal reliability, partial 2-tree, 2-tree, most vital edge
Type
journal article