A New Efficient Approach to Search for All Multi-State Minimal Cuts

摘要

There are several exact or approximating approaches that apply ${rm d}$-MinCuts ($d$-MCs) to compute multistate two-terminal reliability. Searching for and determining $d$-MCs in a stochastic-flow network are important for computing system reliability. Here, by investigating the existing methods and using our new results, an efficient algorithm is proposed to find all the $d$-MCs. The complexity of the new algorithm illustrates its efficiency in comparison with other existing algorithms. Two examples are worked out to show how the algorithm determines all the $d$ -MCs in a network flow with unreliable nodes, and in a network flow of moderate size. Moreover, using the $d$-MCs found by the algorithm, the system reliability of a sample network is computed by the inclusion-exclusion method. Finally, to illustrate the efficacy of using the new presented techniques, computational results on random test problems are provided in the sense of the performance profile introduced by Dolan and Moré.