Diameter constrained reliability of ladders and Spanish fans

We are given a graph G = (V, E), terminal set K  V and diameter d > 0. Links fail stochastically and independently with known probabilities. The diameter-constrained reliability (DCR for short), is the probability that the K-diameter is not greater than d in the subgraph induced by non-failed links. The contributions of this paper are two-fold. First, the computational complexity of DCR-subproblems is discussed in terms of the number of terminals k = jKj and diameter d. Here, we prove that when d > 2 the problem is NP-Hard when K = V. Second, we compute the DCR efficiently for Ladders and Spanish Fans. Open problems and trends for future work are discussed in the conclusions