A Diameter-Constrained Approximation Algorithm of Multistate Two-Terminal Reliability

Abstract

Multistate two-terminal reliability is the probability that d units of flow can be transmitted from the source nodes to the sink node t. It is an important index fora flow network, and its value is based on minpaths or mincuts. However, the enumeration of all minpaths is not feasible in large networks. Hence, designing an approximation algorithm is valuable for the reliability of multistate flow networks. In this paper, we model a multistate flow network as an acyclic directed graph and find that the contribution of minpaths to the reliability changes with their lengths, so we consider the approximation solution of multistate two-terminal reliability by constraining diameter of the network. Furthermore, we give a sufficient and necessary condition to detect irrelevant arcs and propose an approximation algorithm by controlling the value of diameter constraint. In the meantime, the reliability with diameter constraint is also a parameter to partially reflect the performance of network. The experiments demonstrate the effectiveness and efficiency of the algorithm.