Premium
A fast algorithm for reliability calculations in sparse networks
Author(s) -
Spyratos N.,
Bowen A.
Publication year - 1977
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230070304
Subject(s) - reliability (semiconductor) , simple (philosophy) , terminal (telecommunication) , decomposition , algorithm , computer science , series (stratigraphy) , decomposition method (queueing theory) , exponential function , mathematics , mathematical optimization , discrete mathematics , telecommunications , ecology , philosophy , power (physics) , physics , paleontology , mathematical analysis , epistemology , quantum mechanics , biology
The calculation of terminal reliability in other than simple series‐parallel networks takes time exponential in the size of the network. A method is presented for reducing network size by decomposing the network into subnetworks. Terminal reliability is obtained from calculations in the subnetworks. As the efficiency of the method depends on the network decomposition, some simple rules for selecting ‘good’ decompositions are presented. The method yields approximate values of terminal reliability. In sparse networks, however, the approximation is very satisfactory. Further, if the network decomposition satisfies certain conditions, exact values are obtained. Although the method assumes undirected links and perfectly reliable nodes, it can be easily extended to include directed links and failing nodes.