A Fast Algorithm for Searching All Multi-State Minimal Cuts

Evaluating network reliability is an important topic in planning, designing, and control of systems. Many real-world systems are limited-flow (multi-state) networks composed of multi-state components, and their reliabilities can be computed in terms of minimal cut (MC) vectors to leveld(namedd-MC). A straightforward exact algorithm is presented here. The idea is to find alld-MC prior to calculating the limited-flow network reliability between the source, and the sink nodes (i.e. the one-to-one reliability), under the condition that all MC are known in advance. The proposed method is more efficient and effective compared to the existing algorithms in deleting the duplicated-MC, verifyingd-MC candidates, and finding the lower bounds of edge capacities ind-MC. The concepts of the proposed algorithm are novel, and first developed, followed by the analysis of associated computational complexities. Further, an example is provided to illustrate the generation of alld-MC, and verify that the obtainedd-MC are not duplicated.