A Method for Evaluating All the Minimal Cuts of a Graph

This paper presents a new technique to determine all minimal cuts for all the sink nodes in a non-planar network. The algorithm uses a subset method and an iterative process to achieve high efficiency. For an N-sink node network there are (2N - 1) possible combinations of nodes (non-empty subsets). These subsets are checked against several conditions to see if they can be transformed into minimal cutsets. An iterative process is used to generate these non-empty subsets efficiently so that the number of subsets to be checked is about (2N - 1)/2. Since this algorithm generates all the minimal cutsets for all nodes in one operation, it is faster compared to conventional methods which compute for one sink node at a time. Tests using random graphs showed a small cpu time per minimal cutset.