グラフに適応した分散アルゴリズムの設計

本研究では個々のグラフに適応した分散アルゴリズムの設計を行うことを目的とする．従来の最悪計算時に基づく性能の評価では，一部の特殊なインスタンスだけが最悪計算時間になり，その他の多くのグラフでは高速に解くアルゴリズムが存在する場合が考えられる．本研究の課題は(1)グラフの種類を細分化し，特定のグラフに対する高速なアルゴリズムを設計すること(2)グラフ構造に適応した普遍的な最適アルゴリズムを他の問題に対しても考えることが可能であるかを明らかにすることである．今年度は，グラフパラメータの一つである木幅に関して，木幅の近似した値と近似した木分解を分散グラフシステム上で構築するアルゴリズムを研究した．この結果は国際会議SPAAに採択されており高い評価を得ている．また，今回の研究テーマと関連深いモバイルエージェントシステムや逐次型のシステムにおけるパラメータ化アルゴリズムについてもいくつかの結果を得られている．具体的には以下のとおりである．(1)0ビットの永続メモリを持つエージェントと1ビットの永続メモリを持つエージェントの計算能力の解明．特に頂点にO(log n)ビットの書き込み可能なメモリがあり，グラフが2辺連結である場合は両者の計算能力が等価であることを示した．(2)エネルギーシェアリングエージェントモデルにおける循環探索アルゴリズムの解明．グラフの全ての辺を辿り，初期位置に戻るのに必要なエネルギー量の最小値について研究した．(3)最短経路の最致命辺問題に関して，パス幅と削除する辺の本数をパラメータとしてもW[1]困難であることを示した．(1)の結果は国際会議OPODISに採択がされて高い評価が得られている．(2)の結果は国内学会の電子情報通信学会の全国大会で発表をしている．(3)の結果は国内学会の電子情報通信学会に現在投稿をしており発表をする予定である．

本研究では個々のグラフに適応した分散アルゴリズムの設計を行うことを目的とする．従来の最悪計算時に基づく性能の評価では，一部の特殊なインスタンスだけが最悪計算時間になり，その他の多くのグラフでは高速に解くアルゴリズムが存在する場合が考えられる．本研究の課題は(1)グラフの種類を細分化し，特定のグラフに対する高速なアルゴリズムを設計すること(2)グラフ構造に適応した普遍的な最適アルゴリズムを他の問題に対しても考えることが可能であるかを明らかにすることである．今年度は，グラフパラメータの一つである木幅に関して，木幅の近似した値と近似した木分解を分散グラフシステム上で構築するアルゴリズムを研究した．この結果は国際会議SPAAに採択されており高い評価を得ている．また，今回の研究テーマと関連深いモバイルエージェントシステムや逐次型のシステムにおけるパラメータ化アルゴリズムについてもいくつかの結果を得られている．具体的には以下のとおりである．(1)0ビットの永続メモリを持つエージェントと1ビットの永続メモリを持つエージェントの計算能力の解明．特に頂点にO(log n)ビットの書き込み可能なメモリがあり，グラフが2辺連結である場合は両者の計算能力が等価であることを示した．(2)エネルギーシェアリングエージェントモデルにおける循環探索アルゴリズムの解明．グラフの全ての辺を辿り，初期位置に戻るのに必要なエネルギー量の最小値について研究した．(3)最短経路の最致命辺問題に関して，パス幅と削除する辺の本数をパラメータとしてもW[1]困難であることを示した．(1)の結果は国際会議OPODISに採択がされて高い評価が得られている．(2)の結果は国内学会の電子情報通信学会の全国大会で発表をしている．(3)の結果は国内学会の電子情報通信学会に現在投稿をしており発表をする予定である．