Título:
The complexity of the K-reliability in networks constrained to diameter two
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Canale, Eduardo
Cancela, Héctor
Robledo, Franco
Sartor, Pablo
Cancela, Héctor
Robledo, Franco
Sartor, Pablo
Tutor:
Tipo de documento:
Reporte técnico
Editor:
Palabras clave:
Network reliability
Survivability
Diameter constraints
Combinatorial problems
Computational complexity
Formal verification
Survivability
Diameter constraints
Combinatorial problems
Computational complexity
Formal verification
Descriptores:
Año de publicación:
2012
Contenido:
Resumen:
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
Descripción:
Editorial:
UR. FI – INCO.
EN:
Reportes Técnicos 12-09
Financiadores:
Citación:
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.
Citación:
metadata.cc.license.name:
Documento del Gobiberno:
URI:
http://hdl.handle.net/20.500.12008/3465
ISBN:
e-ISBN:
ISSN:
0797-6410
ISMN:
Otros identificadores:
Título Obtenido:
Facultad o Servicio que otorga el Título:
Licencia:
Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Cobertura geográfica:
Cobertura temporal:
metadata.dc.relation.IsVersionOf:
Clasificación:
Es versión de:
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| TR1209.pdf | — | 115.09 KB | Adobe PDF |