Enumeration of All Minimal Cut-Sets for a Node Pair in a Graph

摘要

This paper presents an efficient implicit enumeration algorithm for generating all minimal cut-sets separating a specified node pair in a connected graph. The arcs in the graph need not be directed. By stopping or branching at appropriate levels, the algorithm yields two connected subgraphs, each containing one of the nodes to be separated, with the number of nodes in one of the subgraphs less than any specified value.