組織

専攻

附属センター

関連連携研究機構

関連学部

有向グラフの連結度増大問題に対する効率的なアルゴリズム

二川央笙

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

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

グラフの辺数を削減する前処理の手順
与えられた強連結な有向グラフに対して，2-頂点連結性を担保するために必要な最小本数の追加辺集合を求める問題を取り扱った．この問題に対する既存の多項式時間アルゴリズムに対して計算量の解析を与え，さらに計算量を改善するアルゴリズムを提案した．
修論の感想

なかなか研究が進まないなか，ご指導くださった先生方には本当に感謝しております．いかにして問題を発見し，またそれを発展させるかという点で多くを学んだ二年間でした．

>
ISTyくん

東京大学 THE UNIVERSITY OF TOKYO

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