グラフの向き付けに関する最適化問題の解法

小林　佑輔

（指導教員：岩田 覚 助教授／ 数理情報第3研究室）

研究概要

2k辺連結な無向グラフの各辺に向き付けをしてk枝連結な有向グラフを作る.このような向き付けの中でコストが最小のものを求める問題に対して,既存のアルゴリズムよりも単純で, 計算時間がほぼ同じアルゴリズムを構成した.

卒論の感想

卒論の研究テーマとして, 実装よりも理論的なことを中心に扱わせていただいたので, 興味がある分野の勉強をしながら研究ができ, とても有意義だったと思う.