International Transactions in Operational Research

On computing the 2‐diameter ‐constrained K ‐reliability of networks

Journal Article

  • Author(s): Eduardo Canale, Héctor Cancela, Franco Robledo, Gerardo Rubino, Pablo Sartor
  • Article first published online: 13 Aug 2012
  • DOI: 10.1111/j.1475-3995.2012.00864.x
  • Read on Online Library
  • Subscribe to Journal


This article considers a communication network modeled by a graph G = < V , E > and a distinguished set of terminal nodes K V . We assume that the nodes never fail, but the edges fail randomly and independently with known probabilities. The classical K ‐reliability problem computes the probability that the subnetwork is composed only by the surviving edges in such a way that all terminals communicate with each other. The d ‐diameter ‐constrained K ‐reliability generalization also imposes the constraint that each pair of terminals must be the extremes of a surviving path of approximately d length. It allows modeling communication network situations in which limits exist on the acceptable delay times or on the amount of hops that packets can undergo. Both problems have been shown to be NP ‐hard, yet the complexity of certain subproblems remains undetermined. In particular, when d = 2 , it was an open question whether the instances with | K | > 2 were solvable in polynomial time. In this paper, we prove that when d = 2 and | K | is a fixed parameter (i.e. not an input) the problem turns out to be polynomial in the number of nodes of the network (in fact linear). We also introduce an algorithm to compute these cases in such time and also provide two numerical examples.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.