有向距離空間上の最小ゼロ拡張問題

水谷 隆平

（指導教員：平井 広志 准教授／数理情報第2研究室）

研究概要

有向距離空間上の最小ゼロ拡張問題とは，対称とは限らない距離の定まった有限集合上に新たにいくつかの要素を配置するときに，すべての2要素の組についてのコストと距離の積の和の最小値を求める問題である．本研究では，この問題が多項式時間可解やNP困難となる十分条件を求めた．

有向距離空間とその台グラフの例

卒論の感想

研究の一連の流れを体験することができ，非常に勉強になりました．テーマ決めについては指導教員の先生に頼ってしまったので，今後は良いテーマを自分で見つける能力も養っていきたいです．