Reliabilities of double-loop networks

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.