Graph Algorithms
グラフアルゴリズムの設計と解析
Design and Analysis of Graph Algorithms
研究概要
グラフは，道路網や通信網から分子構造，社会的ネットワークに至るまで，実世界の様々な対象を表現できる強力な数学的構造です．本テーマでは，グラフ上で定義される多様な問題に対して，効率的なアルゴリズムの設計と計算複雑さの理論的解析の両面から取り組んでいます．とくに，グラフのクラスや構造的パラメータに着目した解析により，問題が多項式時間で解ける構造と本質的に困難となる構造との境界を明らかにすることを目指しています．
（ここに図や画像を挿入する予定です）
研究テーマ
制約付きグラフ最適化問題のアルゴリズムと計算複雑性
グラフから所望の性質を満たす部分構造を見つけ出す問題について，アルゴリズムの設計と計算複雑性の解析を行っています．成果として，誘導部分グラフ，全域木，パスカバー，標的集合などの探索アルゴリズムや計算複雑性に関する結果を得ています．
組合せパズルの計算複雑性解析
ペンシルパズルやタイリングといった古典的な組合せパズルを解析する研究にも取り組んでいます．パズルの盤面構造をグラフとして捉えることにより，多項式時間で解けるクラスとNP困難となるクラスの境界を厳密に明らかにしたり，盤面サイズに対する様々なパラメータの上下界を理論的に導出したり，娯楽として親しまれているパズルに潜む豊かな数理構造を浮き彫りにする取り組みです．
関連する発表
- 学術雑誌Takahiro Suzuki, Kei Kimura, Akira Suzuki, Yuma Tamura and Xiao Zhou, "Parameterized complexity of weighted target set selection," Theoretical Computer Science (TCS), vol. 1051, article 115414, pp.1-19, 2025.
- 学術雑誌Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki and Ryuhei Uehara, "Complexity of tiling a polygon with trominoes or bars," Discrete & Computational Geometry (DCG), vol. 58, issue 3, pp. 686-704, 2017.
- 学術雑誌Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa and Takeaki Uno, "Hitori numbers," Journal of Information Processing (JIP), vol. 25, pp. 695-707, 2017.