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/9204 How cite
Title: Network reliability analysis and intractability of counting diameter crystal graphs
Authors: Canale, Eduardo
Robledo Amoza, Franco Rafael
Romero, Pablo
Rubino, Gerardo
Type: Reporte técnico
Keywords: Computational complexity, Network reliability, Diameter-critical graphs
Issue Date: 2016
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.
Publisher: UR.FI-INCO, PEDECIBA Informática
Series or collection: Reportes Técnicos;
ISSN: 0797-6410
Citation: 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
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  
TR1605.pdf159,59 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons