tailieunhanh - Diameter constrained reliability of ladders and Spanish fans

We are given a graph G=(V,E), terminal set K⊆V and diameter d>0. Links fail stochastically and independently with known probabilities. The diameter-constrained reliability (DCR for short) is the probability that the K-diameter is not greater than d in the subgraph induced by non-failed links. | Yugoslav Journal of Operations Research 26 (2016), Number 1, 17–32 DOI: DIAMETER CONSTRAINED RELIABILITY OF LADDERS AND SPANISH FANS H´ector CANCELA Facultad de Ingenier´ıa, Universidad de la Republica ´ cancela@ Franco ROBLEDO Facultad de Ingenier´ıa, Universidad de la Republica ´ frobledo@ Pablo ROMERO Facultad de Ingenier´ıa, Universidad de la Republica ´ promero@ Pablo SARTOR Universidad de Montevideo psartor@ Received: July 2014 / Accepted: January 2015 Abstract: We are given a graph G = (V, E), terminal set K ⊆ V and diameter d > 0. Links fail stochastically and independently with known probabilities. The diameter-constrained reliability (DCR for short) is the probability that the K-diameter is not greater than d in the subgraph induced by non-failed links. The contributions of this paper are two-fold. First, the computational complexity of DCR-subproblems is discussed in terms of the number of terminals k = |K| and diameter d. Here, we prove that if d > 2, the problem is NP-Hard when K = V, and second, we compute the DCR efficiently for ladders and Spanish fans. Keywords: Diameter Constrained Reliability, Computational Complexity, Graph Theory. MSC: 90B15, 90B18, 90B25. 1. INTRODUCTION The diameter-constrained reliability (DCR for short) is a metric that subsumes the classical network reliability (CLR for short). Both metrics serve to model the 18 H. Cancela, F. Robledo, P. Romero, P. Sartor / DCR of Ladders and Spanish Fans reliability of communication networks. Vast literature exists for the CLR, see [5]. The DCR was introduced by [8], inspired in delay-sensitive applications over the Internet infrastructure. It can model situations where there are limits in the acceptable number of hops. Among these we have latency-sensitive contexts, point-to-point and voice-over-IP applications. Arnon Rosethal proved that the CLR is inside the class of NP-Hard problems [10]. As a corollary, the .