Premium
Combinatorial optimization problems in the analysis and design of probabilistic networks
Author(s) -
Bauer D.,
Boesch F.,
Suffel C.,
Tindell R.
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.3230150210
Subject(s) - probabilistic logic , class (philosophy) , vertex (graph theory) , enhanced data rates for gsm evolution , computer science , combinatorics , discrete mathematics , graph , mathematics , mathematical optimization , theoretical computer science , artificial intelligence
This paper presents some results regarding the design of reliable networks. The problem under consideration involves networks which are undirected graphs having equal and independent edge failure probabilities. The index of reliability is the probability that the network fails (becomes disconnected). For “small” edge failure probabilities and given p and q there exists a class of p vertex, q edge graphs with the property that any graph in the class has a smaller probability of disconnection than any graph outside of the class. We solve the problem of synthesizing graphs in this class.