Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2025-01-01T01:55:09.340Z Has data issue: false hasContentIssue false
  • English
  • Français

Some Alternate Characterizations of Reliability Domination

Published online by Cambridge University Press:  27 July 2009

F. T. Boesch ,
A. Satyanarayana  and
C. L. Suffel
F. T. Boesch
Affiliation:
Stevens Institute of Technology Hoboken, New Jersey 07030
A. Satyanarayana
Affiliation:
Stevens Institute of Technology Hoboken, New Jersey 07030
C. L. Suffel
Affiliation:
Stevens Institute of Technology Hoboken, New Jersey 07030
Get access Rights & Permissions [Opens in a new window]

Abstract

An important problem in reliability theory is to determine the reliability of a system from the reliability of its components. If E is a finite set of components, then certain subsets of E are prescribed to be the operating states of the system. A formation is any collection F of minimal operating states whose union is E. Reliability domination is defined as the total number of odd cardinality formations minus the total number of even cardinality formations. The purpose of this paper is to establish some new results concerning reliability domination. In the special case where the system can be identified with a graph or digraph, these new results lead to some new graph-theoretic properties and to simple proofs of certain known theorems. The pertinent graph-theoretic properties include spanning trees, acyclic orientations, Whitney's broken cycles, and Tutte's internal activity associated with the chromatic polynomial.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 4 , Issue 2 , April 1990 , pp. 257 - 276
Copyright
Copyright © Cambridge University Press 1990

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

Agrawal, A. & Barlow, R.E. (1984). A survey of network reliability and domination theory. Operations Research 32: 478–492.CrossRefGoogle Scholar
Barlow, R.E. (1982). Set-theoretic signed domination for coherent structures. Technical Report #ORC 82−1, Operations Research Center, University of California, Berkeley.Google Scholar
Barlow, R.E. & Iyer, S. (1988). Computational complexity of coherent systems and the reliability polynomial. Probability in the Engineering and Information Sciences 2: 461–469.CrossRefGoogle Scholar
Harary, F. (1969). Graph theory. Reading, MA: Addison-Wesley.CrossRefGoogle Scholar
Huseby, A.B. (1984). A unified theory of domination and signed domination with applications to exact reliability computations. Statistical Research Report, Institute of Mathematics, University of Oslo, Norway.Google Scholar
Huseby, A.B. (1989). Domination theory and the crapo β-invariant. Networks 19: 135–149.CrossRefGoogle Scholar
Rodriguez, J. Personal communication.Google Scholar
Satyanarayana, A. (1980). Multi-terminal network reliability. Technical Report ORC 80−6, Operations Research Center, University of California, Berkeley.Google Scholar
Satyanarayana, A (1982). A unified formula for analysis of some network reliability problems. IEEE Transactions on Reliability R-31: 23–32.CrossRefGoogle Scholar
Satyanarayana, A. & Chang, M.K. (1983). Network reliability and the factoring theorem. Networks 13: 107–120.CrossRefGoogle Scholar
Satyanarayana, A. & Hagstrom, J.N. (1981). Combinatorial properties of directed graphs useful in network reliability. Networks 11: 357–366.CrossRefGoogle Scholar
Satyanarayana, A. & Khalil, Z. (1986). On an invariant of graphs and the reliability polynomial. SIAM Journal of Algebraic and Discrete Methods 7: 399–403.CrossRefGoogle Scholar
Satyanarayana, A. & Prabhakar, A. (1978). A new topological formula and rapid algorithm for reliability analysis of complex networks. IEEE Transactions on Reliability R-27: 82–100.CrossRefGoogle Scholar
Satyanarayana, A. & Procesi-Ciampi, R. (1981). On some acyclic orientations of a graph. Technical Report #ORC 81−11, Operations Research Center, University of California, Berkeley.Google Scholar
Satyanarayana, A. & Tindell, R. (1987). Chromatic polynomials and network reliability. Discrete Mathematics 67: 57–79.CrossRefGoogle Scholar
Tutte, W.T. (1954). A contribution to the theory of chromatic polynomials. Canadian Journal of Mathematics 6: 80–91.CrossRefGoogle Scholar
Whitney, H. (1932). A logical expansion in mathematics. Bulletin of the American Mathematical Society 38: 572–579.CrossRefGoogle Scholar