A cut-based algorithm for reliability analysis of terminal-pair network using OBDD

Abstract

In this paper, we propose an algorithm to construct the ordered binary decision diagram (OBDD) representing the cut function of a terminal-pair network. The algorithm recognizes isomorphic sub-problems and thus avoids redundant computations. The system reliability could be efficiently computed by the OBDD. Finally, we propose an approach to compute the importance measures for multiple components by traversing the OBDD only once. The correctness and the effectiveness of our approach are demonstrated by experiments on 30 benchmark networks. The experimental results on a 2-by-100 lattice network, which has 2/sup 99/ paths or 10,000 cuts, show an impressive improvement compared to the previous works using the sum of disjoint products method that have exponential complexity. The CPU time of our method, including the calculation of not only the reliability but also the importance measures, for a 100-stage lattice network is only about 0.24 seconds. Thus, this approach is very helpful for the reliability and sensitivity analysis of large networks.