english Icono del idioma   español Icono del idioma  

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12008/3465 How to cite
Title: The complexity of the K-reliability in networks constrained to diameter two
Authors: Canale, Eduardo
Cancela, Héctor
Robledo, Franco
Sartor, Pablo
Type: Reporte técnico
Keywords: Network reliability, Survivability, Diameter constraints, Combinatorial problems, Computational complexity, Formal verification
Issue Date: 2012
Abstract: Consider a communication network with a set of sites and a set of links between them. Suppose that the sites are perfect but the links can fail independently from one another. Suppose also that at any given instant t, every link xy is operational or failed with probabilities denoted by p(xy) and 1 - p(xy) respectively. Therefore, there is an \201Coperational subnetwork\201D composed by all the sites and only those links that are operational. Computing the network reliability, i.e. the probability that a given subset K of \201Cdistinguished\201D sites are connected on the operational network yielded at t is known as the K-reliability problem and has been widely studied [1]. When additionaly requiring that the operational network be d-K-connected (i.e. that the distance between any pair of sites of K be bounded by a positive integer d) the problem is known as ddiameter- constrained K-reliability (d-DCKR). In this case the reliability is denoted by Rk(G; d). First introduced in [2], this problem has recently gained relevance because it can model situations where limits exist on the acceptable delay times to propagate traffic (like in voice applications over IP networks) or in the amount of hops that packets can undergo (peer-to-peer networks). The general version is known to belong to the NP-hard complexity class [3]. In this paper we prove
Publisher: UR. FI – INCO.
Series or collection: Reportes Técnicos 12-09
ISSN: 0797-6410
Citation: CANALE, E., CANCELA, H., ROBLEDO, F., y otros. "The complexity of the K-reliability in networks constrained to diameter two". Reportes Técnicos 12-09. UR. FI – INCO, 2012.
License: Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Appears in Collections:Reportes Técnicos - Instituto de Computación

Files in This Item:
File Description SizeFormat  
TR1209.pdf115,09 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons