Maximum Flows in Flow Networks Subject to Random ARC Failures

The reliability of directed capacitated networks subject to random arc failures is evaluated by the expected value of maximum flow. It is known that calculating the expected value of maximum flow is very difficult and complicated. An upper bound on the expected value of maximum flow in dire-cted networks is given by Onaga, while a lower bound is found by Carey and Hendrickson. The lower bound sometimes gives the exact value, e.g . , if networks are bipartite. The purpose of this paper is to give necessary and sufficient conditions for a directed network to have the lower bound that is equal to the exact value. Finally, we develop a simple and efficient test that decides whether a given network satisfies the necessary and sufficient conditions and then an illustrative example is introduced.