Minimal cutset enumeration and network reliability evaluation by recursive merge and BDD

Abstract

One of the key tasks in network reliability evaluation is to enumerate all the paths or minimal cutsets of a network. Then the reliability can be calculated from the disjoint form of these terms. Enumerating all the minimal cutsets may be a feasible way to evaluate the reliability of a network if the number of paths is too huge to enumerate practically. One example of this kind of networks is the 2/spl times/100 lattice network. Many algorithms have been proposed to enumerate the minimal cutsets of a graph. Most of them require advanced mathematics or can only be applied to either one of the two broad categories, directed and undirected graphs. This paper presents a simple and systematic recursive algorithm that guarantees the generated cutsets are minimal and the same logic can be applied to both directed and undirected graphs with ease. This algorithm is so simple to implement and efficient that it can also be used to check the correctness of the cutsets generated by the algorithms. This algorithm can also be combined with OBDD (ordered binary decision diagram) to calculate the reliability of a network. Experimental results show that: (1) the running time of enumerating all cutsets versus the graph density is linear for a given number of nodes and (2) it takes 96.71 seconds to evaluate the network reliability of a 2/spl times/100 lattice network which has 2/sup 99/ paths.