Computing the reliability of hammock networks in quadratic time with respect to length

The paper introduces an efficient algorithm for computing the reliability polynomial of hammock networks. A hammock network of length l and width w is made up of w × l identical devices that independently work with probability p (and fail with probability 1 − p ). A brute-force algorithm to compute its reliability polynomial would require a running time exponential in w × l . We introduce a new algorithm and prove that it is exponential in w (as expected), while being only quadratic in l . This allows us to compute, for the first time ever, the reliability polynomials of hammock networks of dimensions significantly larger than 8 (the largest reported in the literature).