Menu
A simple model of an unreliable network is a probabilistic graph in which each edge has an independent probability of being operational. The two-terminal reliability is the probability that specified source and target nodes are connected by a path of operating edges.
Upper bounds on the two-terminal reliability can be obtained from an edge-packing of the graph by source-target cutsets. However, the particular cutsets chosen can greatly affect the bound.
In this paper, we examine three cutset selection strategies, one of which is based on a transshipment formulation of the $k$-cut problem.
These cutset selection strategies allow heuristics for obtaining good upper bounds analogous to the pathset selection heuristics used for lower bounds.
The computational results for some example graphs from the literature provide insight for obtaining good edge-packing bounds. In particular, the computational results indicate that, for the purposes of generating good reliability bounds, the effect of allowing crossing cuts cannot be ignored, and should be incorporated in a good edge-packing heuristic.
This gives rise to the problem of finding a least cost cutset whose contraction in the graph reduces the source-target distance by exactly one.