Title: Diameter-constrained K-reliability evaluation: complexity and heuristics

Authors: Eduardo Canale; Héctor Cancela; Franco Robledo; Pablo Romero; Pablo Sartor

Addresses: Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565 – Código, Postal 11300, Montevideo, Uruguay ' Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565 – Código, Postal 11300, Montevideo, Uruguay ' Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565 – Código, Postal 11300, Montevideo, Uruguay ' Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565 – Código, Postal 11300, Montevideo, Uruguay ' IEEM Business School, Universidad de Montevideo, Lord Ponsonby 2530 – Código, Postal 11600, Montevideo, Uruguay

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 . 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.

Keywords: network reliability; survivability; computational complexity; diameter constraints; K-reliability evaluation; communication networks; polynomial interpolation; subgraphs.

DOI: 10.1504/IJMHEUR.2014.065182

International Journal of Metaheuristics, 2014 Vol.3 No.3, pp.223 - 243

Received: 13 Nov 2013
Accepted: 11 Jun 2014
Published online: 24 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article