Approximate algorithms for network reliability

NR (network reliability) of a connecting graph whose edges may fail with known probabilities and vertices are perfect, is the probability that at least one spanning tree of the graph exists. Then computation problem of NR is, in general, NP-hard. In this paper, two algorithms are proposed for approximating NR by computing upper bound and lower bound of NR: one is the algorithm with O(m) computing time, and another is the algorithm with O(m²/n) computing time, which can give more exact approximation of NR, where m and n are the numbers of edges and vertices, respectively. Particularly, in a group with edges having high reliabilities and a dense graph, a good approximation of NR can be computed by using algorithms presented here. [In Japanese.]