|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b50. 科学研究費助成事業研究成果報告書 >
2015年度 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/13677
|
| タイトル: | グラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの研究 |
| その他のタイトル: | Fixed width parameter algorithms for the graph isomorphism problem |
| 著者: | 大舘, 陽太 |
| 著者（別表記）: | Otachi, Yota |
| キーワード: | グラフアルゴリズム
グラフ同型性判定問題
グラフ幅パラメータ |
| 発行日: | 3-Jun-2016 |
| 抄録: | 連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した．該当論文では，問題そのものを直接解くのではなく，ある種のメタアルゴリズムを作るという方針をとった．グラフ同型性判定の古典的アルゴリズムとして，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
研究分野：グラフアルゴリズム |
| 言語: | jpn |
| URI: | http://hdl.handle.net/10119/13677 |
| 出現コレクション: | 2015年度 (FY 2015)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 25730003seika.pdf | | 198Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
