有向,無効グラフに対する最適なt-spannerの構成について

概要

論文の詳細を見る
非同期式計算機網上での分散アルゴリズムの設計は同期式計算機網上のそれに比べると非常に難しい.その設計法のひとつとして,シンクロナイザという方法を用いて比較的設計のしやすい同期式計算機網上での分散アルゴリズムを非同期式計算機網上でシミュレートすることが提案されている.一般に,分散アルゴリズムの評価はアルゴリズム実行中に送られるメッセージ量(通信複雑度)とアルゴリズムを実行するのに要する時間(時間複雑度)で評価される.同期式計算機上で動作する分散アルゴリズムSをシンクロナイザνによって非同期式計算機上の分散アルゴリズムAに変換したとき,C(A)=C(S)+T(S)C(ν),T(A)=T(S)T(ν)が成り立つ.ここで,C(X),T(X)はそれぞれ分散アルゴリズムの通信複雑度と時間複雑度を表す.従って,シミュレートの際にはシンクロナイザνの通信複雑度C(ν)と時間複雑度T(ν)を小さくすることが必要である.C(ν)とT(ν)は計算機網の形状を表すグラフ(以下,計算機網とその形状を表すグラフを同一視する)のt-spannerと呼ばれる概念と深く関係している.グラフG=(V,E)に対して,次の条件(*)を満たすGの部分グラフH=(V,E')をGのt-spannerという.(*)任意の(u,v)∈Eに対して,dis_H (u,v)≦t.ここで,dis_H (u,v)はHにおけるuからvまでの距離を表す.辺数がm以下のGのt-spannerを(m,t)-spannerと表す.[命題1]グラフGが(m,t)-spannerを持たないとき,Gに対する任意のシンクロナイザνに対して以下の式が成り立つ.T(ν)≧t+1またはC(ν)≧m+1 [命題2]グラフGが(m,t)-spannerを持つとき,T(δ)=O(t)かつC(δ)=O(tm)となるGに対するシンクロナイザδが存在する.G=(V,E)の任意のシンクロナイザνに対してはC(ν)=Ω(|V|),T(ν)=Ω(1)が成り立つので,m=O(|V|)かつt=O(1)となる(m,t)-spanner(このようなspannerを最適spannerと呼ぶ)を求めることが問題となる.本稿では,実用的に重要ないくつかの有向,無向グラフに対して,辺数が点数の2倍以内のt-spannerで最適あるいはほぼ最適となるものが構成できることを示す.
一般社団法人情報処理学会の論文
1989-10-16

有向,無効グラフに対する最適なt-spannerの構成について

スポンサーリンク

概要

著者

関連論文

スポンサーリンク