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

Chin Wen Ho, Sun Yuan Hsieh, Gen Huey Chen

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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.

Original languageEnglish
Pages (from-to)89-113
Number of pages25
JournalJournal of Parallel and Distributed Computing
Volume51
Issue number2
DOIs
StatePublished - 15 Jun 1998

Keywords

  • Network reliability,K-terminal reliability, partial 2-tree, 2-tree, most vital edge

Fingerprint

Dive into the research topics of 'An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees'. Together they form a unique fingerprint.

Cite this