https://scholars.lib.ntu.edu.tw/handle/123456789/488247
標題: | An Efficient Parallel Strategy for Computing K-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees. | 作者: | Ho, Chin-Wen Hsieh, Sun-Yuan GEN-HUEY CHEN |
關鍵字: | Network reliability,K-terminal reliability, partial 2-tree, 2-tree, most vital edge | 公開日期: | 1998 | 卷: | 51 | 期: | 2 | 起(迄)頁: | 89-113 | 來源出版物: | J. Parallel Distrib. Comput. | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0038900397&doi=10.1006%2fjpdc.1998.1454&partnerID=40&md5=9387902a86ef4118e54fcdaf74b657e7 | DOI: | 10.1006/jpdc.1998.1454 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。