2013年 - 2015年
グラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの研究
日本学術振興会 科学研究費補助金(若手研究(B)) 若手研究(B)
- 課題番号
- 25730003
- 体系的課題番号
- JP25730003
- 担当区分
- 研究代表者
- 配分額
-
- (総額)
- 4,160,000円
- (直接経費)
- 3,200,000円
- (間接経費)
- 960,000円
- 資金種別
- 競争的資金
連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した.該当論文では,問題そのものを直接解くのではなく,ある種のメタアルゴリズムを作るという方針をとった.グラフ同型性判定の古典的アルゴリズムとして,Weisfeiler-Lehmanアルゴリズムという手法がある.この論文では,このWeisfeiler-Lehmanを一般化・高速化し,ある種のグラフ幅パラメータが定数の場合に対する固定パラメータ容易性を示した.
関連して,入力グラフがある種の禁止構造を持つ場合を研究した.あるグラフを誘導マイナーとして含まないクラスに対する同型性判定問題に対して計算量二分法を与えた.
関連して,入力グラフがある種の禁止構造を持つ場合を研究した.あるグラフを誘導マイナーとして含まないクラスに対する同型性判定問題に対して計算量二分法を与えた.
- リンク情報
- ID情報
-
- 課題番号 : 25730003
- 体系的課題番号 : JP25730003