Consider a communication network with perfect nodes, links with independent failures, special nodes K called terminals, and a diameter d. The corresponding d-diameter constrained K-reliability (d-DCKR) is the probability that the K terminals remain connected by paths composed by d hops or less. This problem has valuable applications in hop-constrained communication. The general d-DCKR evaluation is NP-Hard. However, we prove that the computational complexity of the 2-DCKR is linear in |K| when |K| is fixed, and an analytic expression for the target probability is provided. We introduce two Monte Carlo-based heuristics to tackle the general d-DCKR problem. The first one connects the target problem with. Numerical experiments with Petersen, dodecahedron and a series-parallel graph confirm the effectiveness of both approaches. The article concludes with a discussion of trends for future work.
['Eduardo A. Canale', 'Héctor Cancela', 'Franco Robledo', 'Pablo Romero', 'Pablo Sartor']
Diameter-constrained K-reliability evaluation: complexity and heuristics