An Efficient Parallel Strategy for Computing K-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees.

Ho, Chin-WenChin-WenHoHsieh, Sun-YuanSun-YuanHsiehGEN-HUEY CHEN2020-05-042020-05-041998https://www.scopus.com/inward/record.uri?eid=2-s2.0-0038900397&doi=10.1006%2fjpdc.1998.1454&partnerID=40&md5=9387902a86ef4118e54fcdaf74b657e7In 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.Network reliability,K-terminal reliability, partial 2-tree, 2-tree, most vital edgeAn Efficient Parallel Strategy for Computing K-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees.journal article10.1006/jpdc.1998.14542-s2.0-0038900397https://doi.org/10.1006/jpdc.1998.1454