dc.contributor | Canale Eduardo, Universidad de la República (Uruguay). Facultad de Ingeniería. | |
dc.contributor | Robledo Amoza Franco, Universidad de la República (Uruguay). Facultad de Ingeniería. | |
dc.contributor | Romero Pablo, Universidad de la República (Uruguay). Facultad de Ingeniería. | |
dc.contributor | Rubino Gerardo, Universidad de la República (Uruguay). Facultad de Ingeniería. | |
dc.creator | Canale, Eduardo | |
dc.creator | Robledo Amoza, Franco Rafael | |
dc.creator | Romero, Pablo | |
dc.creator | Rubino, Gerardo | |
dc.date.accessioned | 2017-07-21T17:31:55Z | |
dc.date.accessioned | 2022-10-28T19:29:41Z | |
dc.date.available | 2017-07-21T17:31:55Z | |
dc.date.available | 2022-10-28T19:29:41Z | |
dc.date.created | 2017-07-21T17:31:55Z | |
dc.date.issued | 2016 | |
dc.identifier | CANALE, Eduardo, ROBLEDO AMOZA, Franco, ROMERO, Pablo, y otros. Network reliability analysis and intractability of counting diameter crystal graphs [en línea]. Montevideo : UR.FI-INCO, PEDECIBA Informática, 2016 | |
dc.identifier | 0797-6410 | |
dc.identifier | http://hdl.handle.net/20.500.12008/9204 | |
dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/4964146 | |
dc.description.abstract | 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. | |
dc.language | en | |
dc.publisher | UR.FI-INCO, PEDECIBA Informática | |
dc.relation | Reportes Técnicos; | |
dc.rights | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) | |
dc.rights | Las obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad de la República.(Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014) | |
dc.subject | Computational complexity | |
dc.subject | Network reliability | |
dc.subject | Diameter-critical graphs | |
dc.title | Network reliability analysis and intractability of counting diameter crystal graphs | |
dc.type | Reporte técnico | |