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

研究成果: 雜誌貢獻期刊論文同行評審

3 引文 斯高帕斯(Scopus)

摘要

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.

原文???core.languages.en_GB???
頁(從 - 到)89-113
頁數25
期刊Journal of Parallel and Distributed Computing
51
發行號2
DOIs
出版狀態已出版 - 15 6月 1998

指紋

深入研究「An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees」主題。共同形成了獨特的指紋。

引用此