鈴木 顕
東北大学 大学院 情報科学研究科

遷移問題とは，ある問題の２つの解が与えられた際に，その一方からもう一方へと段階的に遷移する方法を求める問題である．例えば電力の配電網を，現在のものから，別のものに変更したい場合に，その過程で停電やショートを起こさないように変更するためには，どのような順番でスイッチを操作すれば良いかを求める問題である．遷移問題は他にも，監視カメラの配置等の常時稼働型システムの構成最適化や，インターネット通信等の継続的サービスの提供など，実社会での応用先が非常に多い問題である．

遷移問題は2008年にフレームワークが提案されて以来，世界中で盛んに研究がなされてきた．ところが，生まれる結果は困難性を示すものばかりで，現実社会に貢献できるような結果はほとんどなかった．そのような中，本論文ではパラメータアルゴリズムの概念を，遷移問題に対して適用することで，遷移問題を現実的な時間で解く上で基礎となる理論を与えた．

本論文は，遷移問題に対してパラメータ複雑性の観点からアプローチした世界で初めての論文であり，本論文が発表されて以来，国内外の様々な研究者がこの理論を基に遷移問題にアプローチしており，多くの遷移問題を現実的な時間で解くことが可能になった．

野口研究奨励賞という名誉ある賞を受賞することができ，大変光栄に思っております．情報処理学会東北支部の皆様には深く感謝申し上げます．また，本研究は，周暁先生，伊藤健洋先生，Naomi Nishimura先生のご指導ご支援により遂行することが出来たものです．厚く御礼申し上げます．今後も情報処理分野の発展に貢献できるよう，全力で研究を続けてまいります．