A recursive approach for enumerating minimal cutsets in a network

Abstract

This paper presents a new recursive labelling algorithm for determining all minimal cutsets in a directed network, using an approach adapted from dynamic programming algorithms for the classical shortest route problem. The algorithm produces all minimal cutsets, and uses comparison logic to eliminate any redundant cutsets. Computational experience shows that: (1) the time per cutset varies linearly with the number of nodes but decreases exponentially with the density of the graph; and (2) whereas the algorithm's performance with regard to 'change in the time per cutset vs. the number of nodes' is similar to other algorithms, it appears to exhibit superior performance where the time/cutset is compared to the density of the graph.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>