Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-27T08:16:58.910Z Has data issue: false hasContentIssue false
  • English
  • Français

Reliabilities of Consecutive-2 Graphs

Published online by Cambridge University Press:  27 July 2009

D.Z. Du  and
F. K. Hwang
D.Z. Du
Affiliation:
Massachusetts Institute of Technology Cambridge, Massachusetts 02139
F. K. Hwang
Affiliation:
AT&T Bell Laboratories Murray Hill, New Jersey 07974
Get access Rights & Permissions [Opens in a new window]

Abstract

A consecutive-2 graph is a graph where each vertex is associated with a failure probability and the graph is considered failed if any two adjacent vertices both fail. Recently, the problem of computing reliability for general consecutive-2 graph was shown to be #P-complete while polynomial algorithms exist for trees. In this paper, we give a linear time algorithm for a class of graphs including forests and cycles.

For a given set of failure probabilities qi, the assignment of qi to the vertices of a given graph is optimal if it maximizes the reliability of that graph. It is known that optimal assignments for trees require messy computations while linear algorithms exist for lines and stars. In this paper, we prove that the optimal reliability of any n−tree is bounded between those of an n−line and an n−star.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 1 , Issue 3 , July 1987 , pp. 293 - 298
Copyright
Copyright © Cambridge University Press 1987

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.Antonopoulou, I., & Papastavridis, S.. (1987). Fast recursive algorithm to evaluate the reliability of a circular consecutive-k-out-of-n: F system. IEEE Trans. Reliability R-36: 83–84.Google Scholar
2.Chiang, D. C., & Niu, S. C.. (1981). Reliability of consecutive-k−out−of−n: F systems. IEEE Trans. Reliability R−30, 87–89.CrossRefGoogle Scholar
3.Derman, C., Lieberman, G. J., & Ross, S. M.. (1982). On the consecutive-k−out−of−n system. IEEE Trans. Reliability R-31: 57–63.CrossRefGoogle Scholar
4.Du, D. Z., & Hwang, F. K.. (1986). Optimal consecutive-2-out-of-n systems. Math. Oper. Res. 11: 187–191.CrossRefGoogle Scholar
5.Hwang, F. K. (1982). Fast solutions for consecutive-k−out−of−n system. IEEE Trans. Reliability R−31: 447–448.Google Scholar
6.Hwang, F. K. (1986). Simplified reliabilities for consecutive−k−out−of−n systems. SIAM J. Alg. Disc. Math. 7: 258–264.CrossRefGoogle Scholar
7.Santha, M., & Zhang, Y.. (1987). Consecutive-2 systems on trees. Prob. in the Eng. and Inf. Sciences, forthcoming.Google Scholar
8.Shanthikumar, F. G. (1982). Recursive algorithm to evaluate the reliability of a consecutive-k−out−of−n: F system. IEEE Trans. Reliability R−31: 442–443.CrossRefGoogle Scholar