超大複雑ネットワークの高次探索：グラフ分解理論から実用高速アルゴリズムへの挑戦
【研究分野】情報学基礎
【研究キーワード】
アルゴリズム理論 / グラフマイナー理論 / 指数時間アルゴリズム / ビッグデータ
【研究成果の概要】
Webリンクグラフ、社会ネットワークや巨大地図グラフなどの超大規模ネットワークを、その規模を乗り越えて高速・高次処理するアルゴリズムの設計・解析を目指して、グラフ・ネットワーク理論の基礎成果も創出しながら研究を進めた。具体的には、グラフマイナー理論を超大複雑ネットワークに適用し、情報流通の核となるコア部分と、その他の木的な部分に分解するコア木分解を新たに、その性質を活用した高速最短路クエリ・到達可能性クエリを処理するアルゴリズムを与えた。指数時間アルゴリズムの観点から、厳密に解ける問題サイズを倍などにすることについても固定パラメタ計算複雑度解析を行い、量子計算問題にも適用した。
【研究代表者】
【研究種目】挑戦的萌芽研究
【研究期間】2012-04-01 - 2014-03-31
【配分額】3,900千円 (直接経費: 3,000千円、間接経費: 900千円)