Premium
Network transformations and bounding network reliability
Author(s) -
Brown Jason I.,
Colbourn Charles J.,
Devitt John S.
Publication year - 1993
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.3230230103
Subject(s) - bounding overwatch , upper and lower bounds , reliability (semiconductor) , social connectedness , terminal (telecommunication) , mathematics , polynomial , transformation (genetics) , computer science , mathematical optimization , artificial intelligence , mathematical analysis , computer network , psychology , power (physics) , biochemistry , physics , chemistry , quantum mechanics , psychotherapist , gene
Three transformations on networks that reduce the all‐terminal network reliability (probability of connectedness) of a network are shown not to increase any coefficient in one form of the reliability polynomial of the network. These transformations yield efficiently computable lower bounds on each coefficient of the reliability polynomial. A further transformation due to Lomonosov is shown not to decrease any coefficient in the reliability polynomial, leading to an efficiently computable upper bound on each coefficient. The resulting bounds on coefficients can, in turn, be used to obtain a substantial improvement on the Ball—Provan strategy for computing lower and upper bounds on the all‐terminal reliability. © 1993 John Wiley & Sons, Inc.