組織

専攻

附属センター

関連連携研究機構

関連学部

グラフ上の最適化問題に対するグラフ分解を用いた効率的解法と一般化メークスパン最小化問題の計算量解析

永山 恒彦

（指導教員：定兼 邦彦 教授／数理情報第2研究室）

資料PDF（nagayama.pdf）
研究概要

最大流索引付け問題に対する提案クエリアルゴリズム
第 I 部では最大流索引付け問題などの有向グラフ上の問題に対して，三重連結成分に関するグラフ分解を用いた解法を提案した．第 II 部では一般化メークスパン最小化問題を定式化し，その計算量について解析し，特殊なグラフクラスに対するアルゴリズムを与えた．
修論の感想

定兼教授をはじめとする多くの方に支えられて本稿を完成させることができました．一つのテーマについて掘り下げることに面白さを知ることができたと感じています．

>
ISTyくん

東京大学 THE UNIVERSITY OF TOKYO

Copyright © 2019 　Graduate School of Information Science and Technology, The University of Tokyo