Reliabilities of Double Loop Networks.

A double loop network G (h sub 1, h sub 2) has n nodes represented by the n residues modulo n, and 2n links given by i -> i + h sub 1, i -> i + h sub 2, i = O, 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.