【研究分野】情報学基礎理論

【研究領域課題番号】16K12392 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / 固定パラメタ容易性 / 点モデル / Pottsモデル / Tutte多項式 / グラフ向き付け / 組合せ物理 / Iceモデル / 6点モデル / マトロイド / グラフ / アルゴリズム論 / マトロイドマイナー理論 / アルゴリズム理論

【研究成果の概要】

マトロイドの分解理論とTutte多項式理論の研究を組合せ物理と融合し、計算論的組合せ物理という面からの研究を行った。Iceモデルとその拡張の6点モデルに対して、carving幅に関するFPTアルゴリズム構成した。Pottsモデルで枝幅に関するFPTアルゴリズムも構成した。Tutte多項式に関するMerino-Welsh予想に関して、グラフの枝の向き付けに関する問題を計算解析してTutte予想の一部解決を行った。

【研究の社会的意義】

従来、数理物理において数学と物理の両面から研究されてきた組合せ物理において、計算解析を行うアルゴリズムの開発と、本研究グループメンバが構築した組合せ構造のデータベースを活用した解析を行うことによって、新たに計算論的組合せ物理という研究アプローチを示した。融合する諸分野の理論予想の一部解決も行え、アルゴリズム論からはFPTアルゴリズムの有用性を広げた。物理モデルの量子情報処理との関係を通した量子コンピュータへ研究を展開することが期待できる。

【研究種目】挑戦的萌芽研究

【研究期間】2016-04-01 - 2019-03-31

【配分額】3,380千円 (直接経費: 2,600千円、間接経費: 780千円)