研課題
J-GLOBAL ID:202104009094131164  研究課題コード:16817534

グラフでの詰め込み問題におけるマトロイド性の限界の追究

体系的課題番号:JPMJPR16UR
実施期間:2016 - 2017
実施機関 (1件):
研究代表者: ( , 大学院情報科学研究科, 助教 )
DOI: https://doi.org/10.52926/JPMJPR16UR
研究概要:
「グラフにおいて指定した条件を満たす部分構造を重ならないように選ぶ」ことを目標とする「詰め込み問題」は、相当複雑な条件を課した場合でも効率的に解けることが知られており、その背後には、条件の導く解集合が持つマトロイド的性質があることが明らかになっています。本研究では、そのようなマトロイド性の限界がどこにあるのかを追究し、効率的に解ける問題群に対する1つの特徴付けを与えることを目標とします。
タイトルに関連する用語 (3件):
タイトルに関連する用語
J-GLOBALで独自に切り出した研究課題タイトルの用語をもとにしたキーワードです
研究制度:
上位研究課題: 情報と未来
研究所管機関:
国立研究開発法人科学技術振興機構

前のページに戻る