Premium
Polynomial algorithms for estimating network reliability
Author(s) -
Zemel Eitan
Publication year - 1982
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.3230120408
Subject(s) - reliability (semiconductor) , algorithm , polynomial , function (biology) , time complexity , mathematics , mathematical optimization , existential quantification , computer science , discrete mathematics , mathematical analysis , power (physics) , physics , quantum mechanics , evolutionary biology , biology
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.