通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1

概要

論文の詳細を見る
通信ネットワークの局を点として、リンクを無向辺としてモデル化して得られる無向グラフをこのネットワークのグラフと呼ぶ。通信ネットワークの(σ+1)辺連結化問題((σ+1)ECAN)とは、ネットワークのグラフG=(V, E)がσ辺連結であるときに、C+E′=(V, E∪E′)が(σ+1)辺連結グラフとなる最小の付加辺(リンク)集合E′を求める問題である。また、その分散アルゴリズムとは、ネットワーク上での通信による問題解法のことである。本稿では、σ≥1なる(σ+1)ECANの解で、Gの任意の最小カットを横切る辺数が定数であるようなものを求めるアルゴリズムを与える。さらにその応用として、Gがある条件を満たす場合の(σ+1)ECANに対するT=O(T(|V|, |E|)+|V|), C=O(C(|V|, |E|)+|E|)をもつ分散アルゴリズムDECA-1を提案する。ここで、T(|V|, |E|), C(|V|, |E|)はGのすべての(σ+1)辺連結成分を求める分散アルゴリズムの計算複雑度、通信複雑度を表す。なお、σ=1のときには、T=O(|V|), C=O(|E|)である。
社団法人電子情報通信学会の論文
2000-11-02