著者

関根 京子 今井 浩

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1996, no.100, pp.25-32, 1996-10-17

---

ネットワーク信頼度計算の問題は,一般に#P完全な問題で,大規模ネットワークの信頼度を厳密に実用的時間内で求めることは難しいと思われている.そのため,近似解法として,信頼度の上限下限を多項式時間で求めること,またモンテカルロ法で確率的に近似解を求めることが考えられてきた.後者について,計算量・アルゴリズム理論的観点から,近年,ランダム化(andomizatio)を用いたランダム化FPTAS (andomized Fully Polynomial?Time Approximation Schem)が開発されている.一方,関根,今井は,BDDを援用したネットワーク信頼度の厳密求解法を提案している.本稿では,ネットワーク信頼度計算に対するランダム化FPTAS解法(モンテカルロ法)とBDDを援用する厳密解法の2つについて,後者で得たある程度大きいグラフの厳密な信頼度関数とモンテカルロ法で得た値の比較などを行ない,両者の種々の場面での性質について論じる.Computing the network reliability is a #P-complete problem, and is believed hard to solve if the problem size is large. Recently, randomized fully polynomial-time approximation schemes for computing the network reliability have been developed by Alon, Frieze, Welsh [1] and Karger [15]. There are also proposed several enhanced Monte Carlo methods which utilize lower and upper bounds for the reliability, etc. On the other hand, Sekine and Imai [24] propose an exact approach based on BDDs. By this method, the reliability of a moderate-size network can be computed rigorously. They also present a polynomial-time algorithm for the case of complete graphs. This paper performs compurational experiments, and discusses features of these methods.