Computing Network Reliability Based on Path-Function and BDD

For computing network reliability, most published algorithms are based on the sum of disjoint products.However they lack the capability to avoid redundant computation due to isomorphic sub-problems which are common in the network, and can not be applied to larger networks.To overcome these problems, we present an efficient method which is based on path function and BDD (binary decision diagram) .First, the success path function of a given network is constructed by traversing the network.In this process, the sub-graph isomorphism is efficiently identified.Then in order to further improve performance, we efficiently manipulate the path function using BDD and calculate the reliability measures.The results of experiment show that our method is stable and efficient and can be applied to a number of large-scale networks.