Computing the Probability Mass Function of the Maximum Flow through a Reliable Network

Abstract

This paper proposes a fast state-space enumeration based algorithm called TOP-DOWN capable of computing the probability mass function of the maximum s-t flow through reliable networks. The algorithm computes the probability mass function in the decreasing order of maximum s-t flow values in the network states. This order of enumeration makes this algorithm attractive for commonly observed reliable networks, e.g. in telecommunication networks where link reliabilities are high. It compares the performance of the TOP-DOWN algorithm with a path-based exact algorithm and shows that the TOP-DOWN algorithm solves problem much faster.