Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-16T19:23:35.649Z Has data issue: false hasContentIssue false
  • English
  • Français

Computational Complexity of Coherent Systems and the Reliability Polynomial

Published online by Cambridge University Press:  27 July 2009

R.E. Barlow  and
S. Iyer
R.E. Barlow
Affiliation:
Department of Industrial EngineeringUniversity of California, Berkeley, California 94720
S. Iyer
Affiliation:
Indian Statistical Institute Bombay, India
Get access Rights & Permissions [Opens in a new window]

Abstract

There are three general methods for system reliability evaluation, namely; (1) inclusion–exclusion, (2) sum of disjoint products, and (3) 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. These 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 [5] (cf. [1]). Many of the original set theoretic results are due to Huseby [3]. However, he does not use the reliability polynomial to prove his results.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 2 , Issue 4 , October 1988 , pp. 461 - 469
Copyright
Copyright © Cambridge University Press 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Barlow, R.E. & Agrawal, A. (1984). A survey of network reliability and domination theory. Operations Research 32: 478–492.Google Scholar
2.Barlow, R.E. & Heidtmann, K.D. (1985). k−out−of−n structure reliability. IEEE Transactions on Reliability R-33: 322–323.Google Scholar
3.Huseby, A.B. (1984): A unified theory of domination and signed domination with application to exact reliability computation. Statistical Research Report, Institute of Mathematics, University of Oslo, Norway.Google Scholar
4.Lehman, A. (1964). A solution of the Shannon switching game. Journal for the Society of Industrial and Applied Mathematics 12: 687–725.Google Scholar
5.Satyanarayana, A. & Chang, M.K. (1983). Network reliability and the factoring theorem. Networks 13: 107–120.CrossRefGoogle Scholar