Título:
Network reliability analysis and intractability of counting diameter crystal graphs
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Canale, Eduardo
Robledo, Franco
Romero, Pablo
Rubino, Gerardo
Robledo, Franco
Romero, Pablo
Rubino, Gerardo
Tutor:
Tipo de documento:
Reporte técnico
Editor:
Palabras clave:
Computational complexity
Network reliability
Diameter-critical graphs
Network reliability
Diameter-critical graphs
Descriptores:
Año de publicación:
2016
Contenido:
Resumen:
Consider a stochastic network, where nodes are perfect but links fail independently, ruled by failure probabilities. Additionally, we are given distinguished nodes, called terminals, and a positive integer, called diameter. The event under study is to connect terminals by paths not longer than the given diameter. The probability of this event is called diameter-constrained reliability (DCR, for short). Since the DCR subsumes connectedness probability of random graphs, its computation belongs to the class of NP-Hard problems. The computational complexity for DCR is known for fixed values of the number of terminals k n and diameter d, being n the number of nodes in the network. The contributions of this article are two-fold. First, we extend the computational complexity of the DCR when the terminal size is a function of the number of nodes, this is, when k = k(n). Second, we state counting diameter-critical graphs belongs to the class of NP-Hard problems.
Descripción:
Editorial:
UR.FI-INCO, PEDECIBA Informática
EN:
Reportes Técnicos;
Financiadores:
Citación:
CANALE, E, ROBLEDO, F, ROMERO, P y otros. Network reliability analysis and intractability of counting diameter crystal graphs [en línea]. Montevideo : UR.FI-INCO, PEDECIBA Informática, 2016
Citación:
metadata.cc.license.name:
Documento del Gobiberno:
URI:
http://hdl.handle.net/20.500.12008/9204
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 | ||
|---|---|---|---|---|---|
| TR1605.pdf | — | 159.59 KB | Adobe PDF |