学位論文 単位円グラフのセパレータ構成問題に対するアルゴリズム的研究

後田多, 太一  ,  シイタダ, タイチ  ,  Shiitada, Taichi

pp.1 - 35 , 2016-03-25 , The University of Electro-Communications
内容記述
本研究では単位円グラフ上で良いセパレータを高速に求めることを目的とする.単位円グラフとは単位円の集合に対して各々の単位円を頂点として,単位円どうしが交差するときに辺を張ることによって構成される無向グラフである.無線ネットワークのモデル化などいろいろな応用がある.無向グラフ G=(V,E) 上の頂点集合 V の分割 (S,A,B) で,|A|?2/3|V| かつ |B|?2/3|V| を満たし,A と B の間に辺が存在しないとき,S のことを G のセパレータと呼ぶ.セパレータは分割統治法などで使われることが多く,小さいサイズのセパレータの存在によって効率的なアルゴリズムが考案されている.セパレータのサイズと計算時間の間にはトレードオフの関係があるが,本研究では単位円グラフ上で良いセパレータを高速に求めることを目的として,計算時間が O(|V|log??|V|?) の乱択アルゴリズムを提案する.この乱択アルゴリズムは単位円の集合を直線によって分割することを基にしており,角度 θ∈[0,π) を一様ランダムに選び傾き θ の直線の中でセパレータのサイズが最小となるものを見つけている.計算時間については理論的に求めて,セパレータのサイズの期待値の上界については計算機実験で調べた. 単位円グラフ上のセパレータの先行研究としてJordan曲線上でのセパレータの研究がある.Jordan曲線とは自己交差しない閉じた曲線のことであり,単位円はJordan曲線である.各々のJordan曲線の交差数が有界ならばセパレータのサイズが O(√(|E|)) のセパレータをO(|V|+|E|) の計算時間で求められることが知られている.提案する乱択アルゴリズムは辺数が多いときに先行研究よりも高本研究では単位円グラフ上で良いセパレータを高速に求めることを目的とする.単位円グラフとは単位円の集合に対して各々の単位円を頂点として,単位円どうしが交差するときに辺を張ることによって構成される無向グラフである.無線ネットワークのモデル化などいろいろな応用がある.無向グラフ G=(V,E) 上の頂点集合 V の分割 (S,A,B) で,|A|<_2/3|V| かつ |B|<_2/3|V| を満たし,A と B の間に辺が存在しないとき,S のことを G のセパレータと呼ぶ.セパレータは分割統治法などで使われることが多く,小さいサイズのセパレータの存在によって効率的なアルゴリズムが考案されている.セパレータのサイズと計算時間の間にはトレードオフの関係があるが,本研究では単位円グラフ上で良いセパレータを高速に求めることを目的として,計算時間が O(|V|log|V|) の乱択アルゴリズムを提案する.この乱択アルゴリズムは単位円の集合を直線によって分割することを基にしており,角度 θ∈[0,π) を一様ランダムに選び傾き θ の直線の中でセパレータのサイズが最小となるものを見つけている.計算時間については理論的に求めて,セパレータのサイズの期待値の上界については計算機実験で調べた. 単位円グラフ上のセパレータの先行研究としてJordan曲線上でのセパレータの研究がある.Jordan曲線とは自己交差しない閉じた曲線のことであり,単位円はJordan曲線である.各々のJordan曲線の交差数が有界ならばセパレータのサイズが O(√(|E|)) のセパレータをO(|V|+|E|) の計算時間で求められることが知られている.提案する乱択アルゴリズムは辺数が多いときに先行研究よりも高速であり,セパレータのサイズの期待値も計算機実験より O(√(|E|)) であると予想される.単位円グラフが非連結の場合は連結の場合に帰着できるので,本研究では連結な単位円グラフを扱う.

このアイテムのアクセス数:  回

その他の情報