Please use this identifier to cite or link to this item:
Title: An effective algorithm for computing all-terminal reliability bounds
Other Titles: 10.1002/net.21634
Authors: Silva, Jaime
Gomes, Teresa
Tipper, David
Martins, Lúcia
Kounev, Velin
Keywords: all-terminal network reliability
network availability
binary decision diagram (BDD)
sum of disjoint products
bounds computation
Issue Date: 2015
Publisher: Wiley
Abstract: The exact calculation of all‐terminal reliability is not feasible in large networks. Hence estimation techniques and lower and upper bounds for all‐terminal reliability have been utilized. Here, we propose using an ordered subset of the mincuts and an ordered subset of the minpaths to calculate an all‐terminal reliability upper and lower bound, respectively. The advantage of the proposed new approach results from the fact that it does not require the enumeration of all mincuts or all minpaths as required by other bounds. The proposed algorithm uses maximally disjoint minpaths, prior to their sequential generation, and also uses a binary decision diagram for the calculation of their union probability. The numerical results show that the proposed approach is computationally feasible, reasonably accurate and much faster than the previous version of the algorithm. This allows one to obtain tight bounds when it not possible to enumerate all mincuts or all minpaths as revealed by extensive tests on real‐world networks.
Description: An effective algorithm for computing all-terminal reliability bounds
Peer review: yes
ISSN: 0028-3045
Publisher Version:
Appears in Collections:I&D INESCC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat 
article_networks_Silva_Gomes_Tipper_Martins_Kounev_EstudoGeral.pdf546.07 kBAdobe PDFView/Open

FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.