容量を考慮したネットワークの信頼度

概要

論文の詳細を見る
本報告では,ネットワークの特定の2つのノード間の最大フロウが規定値以上である確率をネットワークの信頼度と定義し,この信頼度を効率的に求める方法を提案する.この問題に対する従来の研究としては,1)全ての最小カット集合を求めて計算する方法,2)陰的列挙法による方法の2つがある.本報告は後者の部類に属する.後者の方法は以下の手順よりなる.i)ネットワークの各要素に番号を付与する.ii)ネットワークの要素からなる部分集合に対して,要素数の少ない順に,また,同じ要素数の場合は要素番号についての辞書的順序によって部分集合を列挙する順序を決定する.iii)順序に従って陰的列挙を行う.この時,ネットワークのリンクまたはカットが見つかる度に陰的列挙の為の条件を更新・削除する.この方法は前者に比べると効率はよいが列挙の順序が全てのネットワークに対して一様に決められているために,陰的列挙が効果的に適用されていない.本報告では,この点を改良し,陰的列挙条件に関する分岐限定法を適用することによりアルゴリズムの改良を行う.
一般社団法人情報処理学会の論文
1989-03-15