グラフでの詰め込み問題におけるマトロイド性の限界の追究
| 体系的番号 |
JPMJPR16UR |
| DOI |
https://doi.org/10.52926/JPMJPR16UR |
研究代表者 |
山口 勇太郎 大阪大学, 大学院情報科学研究科, 助教
|
|---|
| 研究期間 (年度) |
2016 – 2017
|
| 概要 | 「グラフにおいて指定した条件を満たす部分構造を重ならないように選ぶ」ことを目標とする「詰め込み問題」は、相当複雑な条件を課した場合でも効率的に解けることが知られており、その背後には、条件の導く解集合が持つマトロイド的性質があることが明らかになっています。本研究では、そのようなマトロイド性の限界がどこにあるのかを追究し、効率的に解ける問題群に対する1つの特徴付けを与えることを目標とします。
|
|---|
| 研究領域 | 情報と未来 |
|---|
