抄録

A-017
単位円グラフの最小支配集合問題に対する局所並列近似アルゴリズムの提案

無線アドホックネットワークは、無線端末同士が相互に接続する方式をとっている。そのため固定インフラが存在しない一定領域での簡易なネットワークの構築に有効であるが、端末自身が一定のサービスを提供できるネットワークを構築しなければならない。ネットワークでの効率的な通信を行う手段の一つにクラスタリングが存在するが、本研究はそのクラスタリングの理論的高速化を目的とする。ネットワークを単位円グラフでモデル化し、クラスタリングについては支配集合モデルを用いて、任意の単位円グラフに対し支配集合を求める局所並列アルゴリズムを提案する。