Iterative Algorithms for Generating Minimal Cutsets in Directed Graphs

摘要

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 simultaneously 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. (Reprints)