【山口 勇太郎】グラフでの詰め込み問題におけるマトロイド性の限界の追究

研究者

山口 勇太郎

山口 勇太郎

大阪大学
大学院情報科学研究科
助教

研究室ホームページ

研究概要

「グラフにおいて指定した条件を満たす部分構造を重ならないように選ぶ」ことを目標とする「詰め込み問題」は、相当複雑な条件を課した場合でも効率的に解けることが知られており、その背後には、条件の導く解集合が持つマトロイド的性質があることが明らかになっています。本研究では、そのようなマトロイド性の限界がどこにあるのかを追究し、効率的に解ける問題群に対する1つの特徴付けを与えることを目標とします。

プログラム

Program
  • CREST
  • さきがけ
  • ACT-I
  • ERATO
  • ACT-C
  • ACCEL
  • ALCA
  • RISTEX
終了したプログラム
  • パンフレット
  • メールマガジン
  • 契約関連資料
  • マニュアル
  • 女性研究者のみなさまへ
  • 研究成果
  • オープンサイエンス方針
  • ご意見・ご要望