A maximal flow method to search for d-MPs in stochastic-flow networks

Since 1954, the maximal flow problems have gained much attention in the world. They are also extended to many other fields for applications. For example, the definition of a network reliability is just to evaluate the probability of a live connection between the source node and the sink node such that the maximal flow of the network is no less than the demand d. The popular methods in the literature to evaluate the network reliability are mostly through minimal paths (MP) or minimal cuts (MC) of the network. One of them is the three-stages method: (a) searching for all MPs/MCs; (b) searching for all d-MPs (the minimal system states for d via MP)/d-MCs (the maximal system states for d via MC); (c) calculating union probability from these d-MPs/d-MCs. We found that a creative innovation in solving the maximal flow problems may have benefits in the evaluation of network reliability. Based on this idea, this paper proposes a new approach to tackle the problem of searching for all d-MPs by given MPs. The comparisons with the well known algorithm are made for benchmarking. More complicated examples are also examined for illustrative purposes.