通信ネットワークの3辺連結化分散アルゴリズム3DECA

概要

論文の詳細を見る
通信ネットワークの局を点として、リンクを無向辺としてモデル化して得られる無向グラフをこのネットワークのグラフと呼ぶ。通信ネットワークの(σ+1)辺連結化問題((σ+1)ECAN)とは、ネットワークのグラフG=(V, E)がσ辺連結であるときに、G+E′=(V, E∪E′)が(σ+1)辺連結グラフとなる最小の付加辺(リンク)集合E′を求める問題である。また、その分散アルゴリズムとは、ネットワーク上での通信による問題解法のことである。筆者らは、3つの仮定を置いた場合にσ≥1なる(σ+1)ECANの分散アルゴリズムDBCA-1(但し、T=O(T(lVl, lEl)+lVl), C=O(C(lVl, lEl)+lEl)をすでに報告している。ここでは、Gのすべての(σ+1)辺連結成分を求める分散アルゴリズム(σ+1)CECの存在を仮定し、その計算複雑度、通信複雑度をそれぞれT(lVl, lEl), C(lVl, lEl)と表している。なお、σ=1のときには、そのようなT=10(lVl), C=O(lEl)なる分散アルゴリズム2CEC が実際に存在する。本稿では、σ=2のときに、3CECの存在のみを仮定した3ECANの分散アルゴリズム3DECAを提案する。
2001-01-16