バブルソートグラフにおける耐故障経路選択アルゴリズム(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004))

概要

論文の詳細を見る
n-バブルソートグラフは,正則かつ対称なグラフであり,その頂点数,辺数,連結度,直径はそれぞれn!,(n-l)n!/2,n-1,(n-1)/2である.単純で対称な構造をしていることから注目を集めている.本稿では,n-バブルソートグラフを対象とし,頂点から頂点集合への互いに素な経路問題:k-連結グラフにおいて,頂点sと頂点集合D = {d_1:d_2,・・・,d_k}が与えられたとき,sを除いて互いにk本のsからd_i(1≦i≦k)への経路を求めよ;をO(n^5)の時間で解くアルゴリズムを提案する。sからD中のk個の頂点へ向けてマルテキャストを行う際,高々k-1個の停止型故障(辺または頂点)があっても,少くともひとつの頂点はsからのメッセージを受信可能である,という耐故障性をこの問題の解決により達成できる.さらに本稿では,提案されたアルゴリズムが与える経路の長さの総和がO(n^3)であることもあわせて示す.計算機シミュレーションの結果,平均時間計算量,経路長の総和の平均はそれぞれ0(n^<4.7>),0(n^3)となった.
社団法人電子情報通信学会の論文
2004-07-23