On computing the 2‐diameter ‐constrained K ‐reliability of networks. (13th August 2012) - Canale, Eduardo; Cancela, Héctor; Robledo, Franco; Rubino, Gerardo; Sartor, Pablo
Abstract This article considers a communication network modeled by a graph <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3t7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G=<V, E> and a distinguished set of terminal nodes <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3sp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />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 <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3r4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d=2, it was an open question whether the instances with <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3qk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />|K|>2 were solvable in polynomial time. In this paper, we prove that when <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3dm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d=2 and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3gq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />|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.