ive of

Abstract—Two new and efficient algorithms for evaluating the terminal reliability of parallel computer interconnection networks have been proposed. Both the algorithms are based on multiple decomposition approach. The former is meant for reliability evaluation of multi computers while the later is meant for multi stage interconnection networks. Using the first algorithm the reliability of some important multi computer networks based on cubic architecture have been evaluated. The second algorithm is a modified version of the first one, which takes into account the topological advantages of multi stage interconnection networks during the decomposition process. The terminal reliability of some important fault-tolerant multi-stage interconnection networks has been evaluated using the second algorithm for the purpose of comparison. The complexities of the proposed algorithms are found to be highly polynomial in nature. The proposed method of multiple decomposition is compared with some similar decomposition methods. The simulated results confirm that the proposed decomposition method is much better than its counter parts. The generality of the proposed method is assured by applying the same to evaluate the terminal reliability of Alternating group graph which is also an important interconnection network apart from cube like interconnection networks. Index Terms—Probabilistic graph, minimal cut, networ