It is known that a certain case of the all-terminal network reliability can be computed via the
Tutte polynomial which is an invariant in graph theory. Recently, we have proposed a new approach
of computing the Tutte polynomial of a graph of moderate size [9]. In this paper, by using it we
analyze computation method of the general all-terminal network reliability and two-terminal network
reliability with different edge deletion probability. In addition, to obtain the upper bound for the
all-terminal network reliability, the polynomial-time algorithm of computing the Tutte polynomial
for a complete graph [1] is applied to compute that reliability for a complete graph.