Polynomial algorithms for estimating network reliability
Author:
Abstract
We consider the problem of calculating the best possible bounds on the reliability of a system given limited information about the joint density function of its components. We show that a polynomial algorithm for this problem exists iff such an algorithm exists for a certain related problem of minimizing a linear objective function over a clutter. We give numerous examples of network as well as other problems for which the algorithm runs in polynomial time. We also use our construction to prove NP‐hardness for others.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Complexity of network reliability computationsNetworks, 1980
- The Complexity of Enumeration and Reliability ProblemsSIAM Journal on Computing, 1979
- Rational searchInformation Processing Letters, 1979
- Efficient search for rationalsInformation Processing Letters, 1979
- Reducibility among Combinatorial Problems1972
- Matroids and the greedy algorithmMathematical Programming, 1971
- Optimum branchingsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967
- Best Possible Inequalities for the Probability of a Logical Function of EventsThe American Mathematical Monthly, 1965
- Best Possible Inequalities for the Probability of a Logical Function of EventsThe American Mathematical Monthly, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965