Iterative algorithms for generating minimal cutsets in directed graphs

Abstract

Abstract Several approaches for evaluating network reliability require the generation of all minimal cutsets in a directed graph. A general iterative algorithm, based on an underlying algebraic structure, is proposed for generating all minimal s−j cutsets simultancously for all vertices j in such a graph. In order to implement this algorithm in an efficient manner and to exploit sparsity present in the graph, a number of computational simplifications are developed, leading to improved performance of the algorithm. Empirical results show that the choice of certain data structures can have a profound effect on the computational effort required.