Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-28T18:23:38.339Z Has data issue: false hasContentIssue false
  • English
  • Français

Reliabilities of Double-Loop Networks

Published online by Cambridge University Press:  27 July 2009

F.K. Hwang  and
Wen-Ching Winnie Li
F.K. Hwang
Affiliation:
AT&T Bell Laboratories Murray Hill, New Jersey 07974
Wen-Ching Winnie Li
Affiliation:
Department of Mathematics Pennsylvania State University University Park, Pennsylvania 16802
Get access Rights & Permissions [Opens in a new window]

Abstract

A double-loop network G(h1, h2) has n nodes represented by the n residues modulo n and 2n links given by i ↦i + h1, i ↦ i + h2, i = 0,1,…,n – 1.We consider the reliability model where each link fails independently with probability p, the nodes always work, and the network fails if it is not strongly connected. There exists no known polynomial time algorithm to compute the reliabilities of general double-loop networks. When p is small, the reliability is dominated by the link connectivity. As all strongly connected double.loop networks have link connectivity exactly 2, a finer measure of reliability is needed. In this paper we give such a measure and show how to use it to obtain the most reliable double-loop networks.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 5 , Issue 3 , July 1991 , pp. 255 - 272
Copyright
Copyright © Cambridge University Press 1991

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

REFERENCES

Ádám, A. (1967). Research problem 2–10. Journal of Combinatorial Theory 2: 393.Google Scholar
Alspach, B. & Parsons, T.D. (1979). Isomorphism of circulant graphs and digraphs. Discrete Mathematics 25: 97–108.CrossRefGoogle Scholar
Cheng, Y. & Hwang, F.K. (1988). Diameters of weighted double loop networks. Journal of Algorithms 9: 402–410.CrossRefGoogle Scholar
Cheng, Y., Hwang, F.K., Akyildiz, I.F., & Hsu, D.F. (1991). Routing algorithms for double ioop networks (to appear).Google Scholar
Hua, L.G. (1982). Introduction to number theory. New York: Springer-Verlag.Google Scholar
Hwang, F.K. (1981). Cycle polynomial. Proceedings of the American Mathematics Society 83: 215–219.CrossRefGoogle Scholar
Hwang, F.K. & Li, W.W. (1991). Hamiltonian circuits for 2-regular interconnection networks (to appear).Google Scholar
Lenstra, H.W. (1987). Factoring integers with elliptic curves. Annals of Mathematics 126: 649–673.CrossRefGoogle Scholar
van Doom, E.A. (1986). Connectivity of circulant digraphs. Journal of Graph Theory 10: 9–14.CrossRefGoogle Scholar