情報処理学会 第73回全国大会講演要旨

入力として与えられた無向グラフから、各辺が独立に一様な確率Peで消滅し、
さらに始点と終点以外の各頂点が独立に一様な確率Pvで消滅したとする。
この時、このグラフの始点から終点までが連結である確率の上界・下界を多項式時間アルゴリズムによって求める。
また、これらのアルゴリズムの妥当性と計算量、およびシミュレーション実験による値との差についても触れる。