Diameter-constrained K-reliability evaluation: complexity and heuristics. (1st January 2014)

• Record Type: Journal Article
• Authors: Canale, Eduardo; Cancela, Héctor; Robledo, Franco; Romero, Pablo; Sartor, Pablo
• Is Part Of: International journal of metaheuristics. Volume 3:Number 3(2014)
• Page Start: 223
• Page End: 243
• Publication Date: 2014-01-01
• Subjects: network reliability -- survivability -- computational complexity; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

Abstract

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.