Combinatorial optimization problems in the analysis and design of probabilistic networks

Abstract

Abstract 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.