Skip to main content

Research Repository

Advanced Search

An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability

Reed, Sean; Löfstrand, Magnus; Andrews, John

An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability Thumbnail


Authors

Sean Reed

Magnus Löfstrand

JOHN ANDREWS john.andrews@nottingham.ac.uk
Professor of Infrastructure Asset Management



Abstract

An efficient algorithm is presented for computing exact system and survival signatures of K-terminal reliability in undirected networks with unreliable edges. K-terminal reliability is defined as the probability that a subset K of the network nodes can communicate with each other. Signatures have several advantages over direct reliability calculation such as enabling certain stochastic comparisons of reliability between competing network topology designs, extremely fast repeat computation of network reliability for different edge reliabilities and computation of network reliability when failures of edges are exchangeable but not independent. Existing methods for computation of signatures for K-terminal network reliability require derivation of cut-sets or path-sets which is only feasible for small networks due to the computational expense. The new algorithm utilises binary decision diagrams, boundary set partition sets and simple array operations to efficiently compute signatures through a factorisation of the network edges. The performance and advantages of the algorithm are demonstrated through application to a set of benchmark networks and a sensor network from an underground mine.

Citation

Reed, S., Löfstrand, M., & Andrews, J. (2019). An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability. Reliability Engineering and System Safety, 185, 429-439. https://doi.org/10.1016/j.ress.2019.01.011

Journal Article Type Article
Acceptance Date Jan 10, 2019
Online Publication Date Jan 14, 2019
Publication Date May 31, 2019
Deposit Date Jan 22, 2019
Publicly Available Date Mar 29, 2024
Journal Reliability Engineering & System Safety
Print ISSN 0951-8320
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 185
Pages 429-439
DOI https://doi.org/10.1016/j.ress.2019.01.011
Keywords Industrial and manufacturing engineering; Safety, Risk, Reliability and quality
Public URL https://nottingham-repository.worktribe.com/output/1487971
Publisher URL https://www.sciencedirect.com/science/article/pii/S0951832018307907
Additional Information This article is maintained by: Elsevier; Article Title: An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability; Journal Title: Reliability Engineering & System Safety; CrossRef DOI link to publisher maintained version: https://doi.org/10.1016/j.ress.2019.01.011; Content Type: article; Copyright: © 2019 Elsevier Ltd. All rights reserved.

Files




You might also like



Downloadable Citations