Algorithms for Restricted Matching Problems (制約付きマッチング問題に対するアルゴリズム)

殷 信

（指導教員：室田一雄 教授／数理情報第2研究室）

研究概要

グラフ理論において重要なテーマの一つであるマッチング問題についての研究である。その中でもハミルトン閉路問題と関わりの深い2マッチング問題に対する一般化問題の計算量を調べたものとなっている。特に異なる禁止グラフに対して、tマッチング問題が多項式時間可解である必要十分条件を考案した。

禁止グラフの縮小における工夫

卒論の感想

学術研究を行う上で、常に厳密性を追求する必要があることを実感することができました。そして，卒論研究にあたり，先生方に大変お世話になりました。感謝の気持ちを胸にこれからも頑張りたいと思います。