On the Reliability of Series-Parallel Networks in Grid Graphs

We consider a directed rectangular grid with one source and one sink such that its arcs are directed either to the right or up and have an equal functioning probability. In this paper under network reliability we assume the probability that there is at least one path containing no failed edge from the source to the sink. Because the problem of the grid reliability calculation is NP-hard, the estimates of the network reliability that can be computed in polynomial time are of interest. This paper deals with the problem of finding the most reliable series-parallel network, its reliability will be the lower bound of the grid reliability.