A novel method for the network reliability in terms of capacitated-minimum-paths without knowing minimum-paths in advance

Abstract

Many real-world systems (such as electric power, transportation, etc) may be regarded as flow networks whose arcs have independent, discrete, limited and multivalued random capacities. In this study, a novel method for the network reliability is present. Analysis of the proposed algorithm and comparison to existing best-known algorithms shows that the proposed method has the following advantages: (1) it is just based on the special property of capacitated-minimum-paths (CMPs) of which the max-flow in these paths are all equal to a given capacity (say d) and can be used to search for all capacitated minimum-paths without knowing all minimum-paths in advance; (2) it is simple and more effective in finding CMP candidates than the existing methods and (3) the proposed method is easier to understand and implement.

Keywords:

• reliability
• limited-flow network
• minimum-path
• capacitated-minimum-path
• max-flow

Acknowledgements

I wish to thank both the chief editor and referees for their constructive comments and recommendations, which have significantly improved the presentation of this paper. This research was supported in part by the National Science Council of Taiwan, ROC under Grant no. NSC 91-2213-E-035-029.