電子情報通信学会総合大会講演要旨
DS-1-2
分散型オンライングラフ探索問題
◎八神貴裕・山内由紀子・来嶋秀治・山下雅史(九大)
グラフ内を逃げ回る侵入者を複数の移動する探索者が発見するグラフ探索問題を考える.
本稿では,探索者が事前にグラフを知ることができないオンライン探索を考える.
各探索者はメモリを所有し,固有の識別子を持つ.
探索者は同一点上の他の探索者と情報交換ができ,互いに協力して探索する.
各探索者は異なる頂点から同じアルゴリズムに基づいて探索する.
オンライングラフ探索問題では,探索者達が1つの頂点に集合する問題が重要な部分問題になる.
本稿では,探索者がグラフ内の1つの頂点に集合するアルゴリズムを提案し,それをサブルーチンとして用いるオンライングラフ探索アルゴリズムを提案する.
さらに,このアルゴリズムを用いて,探索に必要十分な最小探索者数を考察する.