𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Combinatorial optimization problems in the analysis and design of probabilistic networks

✍ Scribed by D. Bauer; F. Boesch; C. Suffel; R. Tindell

Publisher
John Wiley and Sons
Year
1985
Tongue
English
Weight
668 KB
Volume
15
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Probabilistic analysis of an asymptotica
Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem
✍ C.T. Ng; X. Cai; T.C.E. Cheng πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 135 KB πŸ‘ 2 views

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well-known NP-hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optima