共同研究・競争的資金等の研究課題

2015年4月 - 2017年3月

部分グラフ探索問題におけるアルゴリズムの設計とその計算複雑さについての解明

日本学術振興会  科学研究費助成事業 特別研究員奨励費
  • 江藤 宏

課題番号
15J05484
配分額
(総額)
1,900,000円
(直接経費)
1,900,000円

まず,研究業績として「最大d独立頂点集合問題」「誘導閉路探索問題」「支配閉路探索問題」「誘導部分グラフにおける新たな特徴についての研究」がある.
「最大d独立頂点集合問題」について,平成28年度に3件の国際会議への公表を行い,2件の国内発表を行った.また,この研究課題について学会誌への投稿している.さらに,標題「An Improved Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs」で平成29年5月に公表を行う.
「誘導閉路探索問題」においては,1件の国際会議への投稿を行った.また,正則誘導部分グラフ探索問題との関連性について雑誌論文への投稿を予定している.
「支配閉路探索問題」について,正則性のひとつである閉路による頂点支配集合問題への拡張を行った.この研究成果について,2件の国内発表を行った.また,この研究課題について雑誌論文への投稿している.
最後に,誘導部分グラフにおける新たな特徴についての研究をおこなった.誘導部分グラフ探索問題において,特徴が遺伝性を持つ問題については既に研究成果があった.そこで,申請書にもあるように遺伝性の無い特徴について今まで研究を行い,中でも,遺伝性の無い特徴として「正則性」を取り扱ってきた.新たな特徴として,正則性の拡張の一つともいえる「グリッド性」について研究を行った.これは,遺伝性のある「平面性」との関係も深い.この研究課題について,標題「On the Maximum Induced Subgraph Problem with the Grid and Cycle」で平成29年5月に公表を行う.さらに,他にも遺伝性の持たない特徴について複数の研究成果を得ており,公表予定である.

ID情報
  • 課題番号 : 15J05484