分散グラフアルゴリズム

分散グラフシステムにおけるアルゴリズムの設計や計算困難性について研究を行っています。複数の計算機が参加するシステムでは、ネットワークの規模が大きくなるにつれ全体の情報を各計算機が知るのは困難になります。そのため、各計算機は自身とネットワークで接続している計算機との局所的な通信によって大域的な問題を解くことが重要となります。私の研究ではネットワークをグラフと見なして、そのグラフ上で局所通信によってどのような問題が効率的に解けるかや効率的に解くことが不可能であるかについて研究をしています。