Computing the reliability of hammock networks in quadratic time with respect to length
提出一种高效算法，能在宽度指数时间、长度二次时间内计算吊床网络的可靠性多项式，首次支持计算尺寸大于8的网络。
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).