Diameter-constrained K-reliability evaluation: complexity and heuristics
by Eduardo Canale; Héctor Cancela; Franco Robledo; Pablo Romero; Pablo Sartor
International Journal of Metaheuristics (IJMHEUR), Vol. 3, No. 3, 2014

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.

Online publication date: Wed, 15-Oct-2014

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Metaheuristics (IJMHEUR):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com