Computational Complexity of Coherent Systems and the Reliability Polynomial

摘要

There are three general methods for system reliability evaluation, namely; inclusion-exclusion, sum of disjoint products, and pivoting. Of these, only pivoting can be applied directly to a logic tree or network graph representation without first finding minimal path (or cut) sets. Domination theory provides the basis for selecting optimal pivoting strategies. Simple proofs of domination-theory results for coherent systems are given, based on the reliability polynomial. There results are related to the problem of finding efficient strategies for computing coherent system reliability. The original results for undirected networks are due to Satyanarayana and Chang. Many of the original set theoretic results are due to Huseby. However, he does not use the reliability polynomial to prove his results. Keywords: Reprints. (KR)