ローテータグラフにおける頂点から頂点集合への互いに素な経路問題

概要

論文の詳細を見る
n-ローテータグラフは, 正則かつ対称な有向グラフであり, その頂点数, 辺数, 直径, 連結度はそれぞれn!, (n-1)n!, n-1, n-1である.n-ハイパキューブなどと比べて集積度が高いことから, ローテータグラフは最近注目を集めている.本稿では, n-ローテータグラフを対象とし, 頂点から頂点集合への互いに素な経路問題:k-連結グラフにおいて, 頂点sと頂点集合T={t_1, t_2, …, t_k}が与えられたとき, sを除いて互いに素なk本の経路s⟶t_i(1≤i≤k)を求めよ, をO(n^5)の時間で解く算法を提案する.sからT中のk個の頂点へ向けてマルチキャストを行う際, 高々k-1個の停止型故障(辺または頂点)があっても, 少くともひとつの頂点はsからのメッセージを受信可能である, という耐故障性をこの問題解決により達成できる。さらに本稿では, 提案された算法が与える経路の長さの総和がO(n^3)であることもあわせて示す.計算機シミュレーションの結果, 平均時間計算量, 経路長の総和の平均はそれぞれO(n^4), O(n^<2.7>)となった.
社団法人電子情報通信学会の論文
2000-10-05