Recently, fully polynomial randomized approximation scheme for computing the network reliability have
been developed by Alon, Frieze, Welsh [1] and Karger [10]. Since the computation of the network reliability
is #P-hard, developing such approximation scheme is important, while still it is required to develop a new
paradigm to compute the network reliability exactly for moderate-size problems.
This paper proposes a unified approach by means of the binary decision diagram, BDD in short, to solve
#P-hard problems related to the network reliability efficiently. Specifically, for the following #P-hard
problems
ffl All-terminal and two-terminal undirected network reliability with different edge deletion probability,
ffl Counting the number of paths between two terminals in undirected and directed cases,
our approach provides algorithms running
ffl in O(n O(n ff ) ) time for a class of O(n ff )-separable graph with n vertices (0 ! ff ! 1),
ffl in O(2 O(
p
n) ) time for planar graphs.
In fact, for any class of graphs having a good elimination ordering, this paradigm provides efficient solutions.