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

2013年 - 2015年

グラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの研究

日本学術振興会  科学研究費補助金(若手研究(B))  若手研究(B)

課題番号
25730003
体系的課題番号
JP25730003
担当区分
研究代表者
配分額
(総額)
4,160,000円
(直接経費)
3,200,000円
(間接経費)
960,000円
資金種別
競争的資金

連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した.該当論文では,問題そのものを直接解くのではなく,ある種のメタアルゴリズムを作るという方針をとった.グラフ同型性判定の古典的アルゴリズムとして,Weisfeiler-Lehmanアルゴリズムという手法がある.この論文では,このWeisfeiler-Lehmanを一般化・高速化し,ある種のグラフ幅パラメータが定数の場合に対する固定パラメータ容易性を示した.
関連して,入力グラフがある種の禁止構造を持つ場合を研究した.あるグラフを誘導マイナーとして含まないクラスに対する同型性判定問題に対して計算量二分法を与えた.

リンク情報
URL
https://kaken.nii.ac.jp/d/p/25730003.ja.html
KAKEN
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-25730003
ID情報
  • 課題番号 : 25730003
  • 体系的課題番号 : JP25730003