Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form
D-Scholarship @ Pitt Banner and Links to Homepage

An Effective Algorithm for Computing All-terminal Reliability Bounds

Silva, Jaime and Gomes, Teresa and Tipper, David and Martins, Lucia and Kounev, Velin (2015) An Effective Algorithm for Computing All-terminal Reliability Bounds. Networks, 66 (4). 282 - 295.

[img] Plain Text (licence)
Available under License : See the attached license file.
Download (1kB)

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.

Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: Article
Status: Published
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Silva, Jaime
Gomes, Teresa
Tipper, Daviddtipper@pitt.eduDTIPPER0000-0002-9429-6425
Martins, Lucia
Kounev, Velinvkounev@pitt.eduVKOUNEV
Date: 5 December 2015
Date Type: Publication
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Journal or Publication Title: Networks
Volume: 66
Number: 4
Publisher: Wiley
Page Range: 282 - 295
DOI or Unique Handle: 10.1002/net
Institution: University of Pittsburgh
Schools and Programs: School of Information Sciences > Telecommunications
Refereed: Yes
Article Type: Research Article
Date Deposited: 23 Nov 2015 15:06
Last Modified: 03 Jun 2019 14:55
URI: http://d-scholarship.pitt.edu/id/eprint/26387

Metrics

Monthly Views for the past 3 years

Plum Analytics

Altmetric.com

Actions (login required)

View Item View Item