An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees |
| |
| Authors: | Chin-Wen Ho Sun-Yuan Hsieh Gen-Huey Chen |
| |
| Affiliation: | aDepartment of Computer Science and Information Engineering, National Central University, Chung-Li, Taiwan;bDepartment of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan |
| |
| 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(log n) 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. |
| |
| Keywords: | Network reliability K-terminal reliability partial 2-tree 2-tree most vital edge |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
