Proj
J-GLOBAL ID：202104009094131164
Research Project code：16817534
グラフでの詰め込み問題におけるマトロイド性の限界の追究
グラフでの詰め込み問題におけるマトロイド性の限界の追究
National award number：JPMJPR16UR
Study period：2016 - 2017
Organization (1)：
Principal investigator：
(
, 大学院情報科学研究科, 助教 )
DOI：
https://doi.org/10.52926/JPMJPR16UR
Research overview：
「グラフにおいて指定した条件を満たす部分構造を重ならないように選ぶ」ことを目標とする「詰め込み問題」は、相当複雑な条件を課した場合でも効率的に解けることが知られており、その背後には、条件の導く解集合が持つマトロイド的性質があることが明らかになっています。本研究では、そのようなマトロイド性の限界がどこにあるのかを追究し、効率的に解ける問題群に対する1つの特徴付けを与えることを目標とします。
Terms in the title (3)：
Terms in the title
Keywords automatically extracted from the title.
,
,
Research program：
＞
＞
Parent Research Project：
情報と未来
Organization with control over the research：
Japan Science and Technology Agency
