A fast method for enumerating all minimal d-cut-sets in a flow network

A d-cut-set in a flow network is a set of components whose removal or blockage causes the maximum flow (MF) to fall below value d, provided that in fully operational network MF is greater or equal to d. A min-d-cutset is a d-cut set such that it does not contain any other d-cut-set. In turn, a cut-set is a set of components whose removal disconnects the source and the sink, which results in MF being equal to 0. A min-cut-set contains no other cut-set. The method works as follows: the min-cut-sets are ordered according to increasing flow capacities, then from every min-cut-set a number of d-cut-sets are generated and each of them is checked for being minimal and unique. The method features two different algorithms respectively applied if Φ(C) < 2d or Φ(C) ≥ 2d. C is the min-cut-set from which d-cut-sets are generated, and Φ(C) is the flow capacity of C. This distinction results in quick generation of min-d-cut-sets without finding many non-d-cut-sets or nonminimal d-cut-sets. Compared to the similar methods, the new one is highly efficient, due to several original solutions, e.g. an efficient method of checking the redundancy of candidates for min-d-cut-sets. Min-d-cut-sets have two main applications. First, they can be used to compute various reliability characteristics of flow networks. Second, the knowledge of these sets facilitates or even enables management and maintenance of various flow networks such as data transmission, water, power supply, or traffic networks, field drainage systems, etc.