並列タイトル等Fixed width parameter algorithms for the graph isomorphism problem
一般注記連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した.該当論文では,問題そのものを直接解くのではなく,ある種のメタアルゴリズムを作るという方針をとった.グラフ同型性判定の古典的アルゴリズムとして,Weisfeiler-Lehmanアルゴリズムという手法がある.この論文では,このWeisfeiler-Lehmanを一般化・高速化し,ある種のグラフ幅パラメータが定数の場合に対する固定パラメータ容易性を示した.関連して,入力グラフがある種の禁止構造を持つ場合を研究した.あるグラフを誘導マイナーとして含まないクラスに対する同型性判定問題に対して計算量二分法を与えた. : We showed that the graph isomorphism problem is fixed-parameter tractable when parameterized by root-connected tree distance width. To show the result, we modified the classic Weisfeiler-Lehman algorithm so that it works not only for all vertex subsets of size k but also for restricted family of vertex subsets of size k. Furthermore, the modified algorithm runs in FPT time with the parameter k. Then we showed that we can apply the algorithm to the graph isomorphism problem parmeterized by several graph width parameters including root-connected tree distance width. We also studied the graph isomorphism problem for graph classes forbidding a single graph as an induced minor. We showed a complexity dichotomy with respect to the forbidden induced minor.
若手研究(B)
研究期間:2013~2015
課題番号:25730003
研究者番号:80610196
研究分野:グラフアルゴリズム
identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/13677
一次資料へのリンクURLhttps://dspace.jaist.ac.jp/dspace/bitstream/10119/13677/1/25730003seika.pdf
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース(IRDB)(機関リポジトリ)
提供元機関・データベース北陸先端科学技術大学院大学 : JAIST学術研究成果リポジトリ