1. 前のページに戻る

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

研究課題

戦略的な研究開発の推進 戦略的創造研究推進事業 ACT-I

体系的番号 JPMJPR16UR
DOI https://doi.org/10.52926/JPMJPR16UR

研究代表者

山口 勇太郎  大阪大学, 大学院情報科学研究科, 助教

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

URL: 

JSTプロジェクトデータベース掲載開始日: 2017-03-22   JSTプロジェクトデータベース最終更新日: 2025-03-26  

サービス概要 よくある質問 利用規約

Powered by NII jst