Por favor, use este identificador para citar o enlazar este ítem:
https://hdl.handle.net/20.500.12008/9204
Cómo citar
Título: | Network reliability analysis and intractability of counting diameter crystal graphs |
Autor: | Canale, Eduardo Robledo, Franco Romero, Pablo Rubino, Gerardo |
Tipo: | Reporte técnico |
Palabras clave: | Computational complexity, Network reliability, Diameter-critical graphs |
Fecha de publicación: | 2016 |
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. |
Editorial: | UR.FI-INCO, PEDECIBA Informática |
Serie o colección: | Reportes Técnicos; |
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 |
ISSN: | 0797-6410 |
Licencia: | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) |
Aparece en las colecciones: | Reportes Técnicos - Instituto de Computación |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | ||
---|---|---|---|---|---|
TR1605.pdf | 159,59 kB | Adobe PDF | Visualizar/Abrir |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons