A simple algorithm to search for all MCs in networks
Evaluating the network reliability is an important topic in the planning, designing, and control of systems. The minimal cut (MC, an edge set) set is one of the major and fundamental tools for evaluating the network reliability. In this study, an alternative method is given to define a MC using a node set (called MCV). A very simple algorithm based on some intuitive theorems that characterize the structure of the MCV and the relationship between MC and MCV is developed to find the MCs between two special nodes. The proposed algorithm is then generalized to find all MCs between all pairs of nodes. The proposed algorithm is not only easier to understand and implement, but is also better than the existing best-known algorithm. The correctness of the proposed algorithm will be analyzed and proven. One example is illustrated to show how all MCs are generated and verified in a network using the proposed algorithm.
algorithm network reliability minimal cuts (mc)