|
JAIST Repository >
School of Information Science >
Grants-in-aid for Scientific Research Papers >
FY 2015 >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10119/13677
|
| Title: | グラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの研究 |
| Other Titles: | Fixed width parameter algorithms for the graph isomorphism problem |
| Authors: | 大舘, 陽太 |
| Authors(alternative): | Otachi, Yota |
| Keywords: | グラフアルゴリズム
グラフ同型性判定問題
グラフ幅パラメータ |
| Issue Date: | 3-Jun-2016 |
| Abstract: | 連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した．該当論文では，問題そのものを直接解くのではなく，ある種のメタアルゴリズムを作るという方針をとった．グラフ同型性判定の古典的アルゴリズムとして，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. |
| Description: | 若手研究(B)
研究期間：2013～2015
課題番号：25730003
研究者番号：80610196
研究分野：グラフアルゴリズム |
| Language: | jpn |
| URI: | http://hdl.handle.net/10119/13677 |
| Appears in Collections: | 2015年度 (FY 2015)
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 25730003seika.pdf | | 198Kb | Adobe PDF | View/Open |
|
All items in DSpace are protected by copyright, with all rights reserved.
|
