Proceedings of the Eighth IEEE Symposium on Computers and Communications. ISCC 2003
Download PDF

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 2x100 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 other 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 2x100 lattice network which has 299 paths.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!

Related Articles