An Efficient Parallel Strategy for Computing K-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees
Source: Journal of Parallel and Distributed Computing, Volume 51, Number 2, June 1998 , pp. 89-113(25)
Publisher: Academic Press
Abstract:In this paper, we first develop a parallel algorithm for computing K-terminal reliability, denoted by R(GK), in 2-trees. Based on this result, we can also compute R(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 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 time. Copyright 1998 Academic Press.
Document Type: Research Article
Affiliations: 1: Department of Computer Science and Information Engineering, National Central University, Chung-Li, Taiwan 2: Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan
Publication date: 1998-06-01