平衡な有向グラフに対するカットを近似したグラフの疎性化

池田 基樹

（指導教員：谷川 眞一 准教授／ 数理情報第7研究室）

研究概要

無向グラフの疎な部分グラフによって全てのカットの重みを近似するカット近似グラフ疎性化という手法を，ある種の平衡な有向グラフに対して拡張した．この手法を前処理として用い，有向グラフの最小カット問題の近似アルゴリズムの時間計算量を改善した．

グラフの疎性化

卒論の感想

研究を進める中で様々な分野への関連や接続を知ることができました．今回得た経験や知識を今後の研究生活にも活かしていければと思います．