2連結成分更新問題を解く分散アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
本稿では, 2連結成分更新問題を解く分散アルゴリズムを示す. 2連結成分更新問題とは, 2連結成分が既に求まっているネットワークにおいて, ネットワークのトポロジー変化が生じたときに, トポロジー変化に応じて, 2連結成分を更新する問題である. 本稿では, いくつかのプロセッサとリンクの追加や削除に対して, 2連結成分更新問題を解くメッセージ計算量O(n'+a+b), 理想時間計算量O(n')の分散アルゴリズムを提案する. ここで, n'はトポロジー変化後のネットワークのプロセッサ数, aは追加リンク数を表す. また, bは, 削除リンクを含む(トポロジー変化前の)2連結成分のリンク数の合計を表す. また, 切断点更新問題, 橋更新問題, 強連結成分更新問題についても触れる.
社団法人電子情報通信学会の論文
1996-01-26

著者

関連論文

もっと見る

スポンサーリンク