Threshold Reliability of Networks with Small Failure Sets

dc.contributor.authorBall, Michael O.en_US
dc.contributor.authorHagstrom, Jane N.en_US
dc.contributor.authorProvan, J. Scotten_US
dc.description.abstractThis paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. For the network flow model we are given a capacitated source/sink graph in which arcs fail randomly. The system is defined as operating whenever the max-flow value is greater than a threshold. For the project scheduling model we are given a directed acyclic source/sink graph in which each arc has two lengths. Each arc randomly takes on one of two states. In the "operating" state it takes on its smaller length and in its "failed" state it takes on it larger length. The system is defined as operating whenever the length of the longest path is less than a threshold. We address a special case of the threshold flow problem in which all arcs have the same capacity and a special case of the project scheduling model in which the difference between the lower and higher arc lengths is constant. For these special cases we show that if the underlying systems are 1-critical, namely, all arcs are in some cutset of size two, then the threshold flow problem can be solved in polynomial time and planar project scheduling problem can be solved in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path. We also show how the basic approach can be used to generate bounds for systems that are "almost critical".en_US
dc.format.extent1551376 bytes
dc.relation.ispartofseriesISR; TR 1993-43en_US
dc.subjectnetwork reliability network flowen_US
dc.subjectproject schedulingen_US
dc.subjectCommunication en_US
dc.subjectSignal Processing Systemsen_US
dc.titleThreshold Reliability of Networks with Small Failure Setsen_US
dc.typeTechnical Reporten_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1.48 MB
Adobe Portable Document Format