Diameter-constrained K-reliability evaluation: complexity and heuristics. (1st January 2014) - Canale, Eduardo; Cancela, Héctor; Robledo, Franco; Romero, Pablo; Sartor, Pablo
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 polynomial interpolation theory, while the second counts subgraphs. 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.