Premium
The most reliable series‐parallel networks
Author(s) -
Neufeld Eric M.,
Colbourn Charles J.
Publication year - 1985
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.3230150104
Subject(s) - series (stratigraphy) , reliability (semiconductor) , series and parallel circuits , computer science , probabilistic logic , simple (philosophy) , enhanced data rates for gsm evolution , function (biology) , measure (data warehouse) , mathematics , algorithm , artificial intelligence , data mining , paleontology , power (physics) , philosophy , physics , epistemology , quantum mechanics , voltage , evolutionary biology , biology
The design of reliable communications networks is an interesting and important topic. Perhaps the most common measure of reliability is a probabilistic one: the probability that a network is connected given the possibility of statistically independent line failures. In general, this is not efficiently computable. In this article, we develop a formula for the reliability of the most reliable maximal series‐parallel networks. The most reliable maximal series‐parallel networks are those maximal series‐parallel networks with the minimum number of vertices of degree 2, independent of many of the simpler reliability estimates. A two‐dimensional recurrence relating networks of varying sizes and edge deficiencies provides a generating function which in turn is exploited to give a simple closed expression for reliability.