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

Material type: 文書・図像類

Author: 大舘, 陽太

Publisher: -

Publication date: 2016-06-03

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: 連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した．該当論文では，問題そのものを直接解くのではなく，ある種のメタアルゴリズムを作るという方針をとった．グラフ同型性判定の古典的アルゴリズムとして，Weisfeiler-Lehmanアルゴリズムという手法がある．この論文では，...

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

JAIST Repository
Digital
You can check the holdings of institutions and databases with which 学術機関リポジトリデータベース（IRDB）（機関リポジトリ） is linked at the site of 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）.
JAIST Repository

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 文書・図像類
Title: グラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの研究
Author/Editor: 大舘, 陽太
Author Heading: 大舘, 陽太
Publication Date: 2016-06-03
Publication Date (W3CDTF): 2016-06-03
Alternative Title: Fixed width parameter algorithms for the graph isomorphism problem
Periodical title: 科学研究費助成事業研究成果報告書
Pages: 1-5
Text Language Code: jpn
Subject Heading: グラフアルゴリズム
グラフ同型性判定問題
グラフ幅パラメータ
Target Audience: 一般
Note (General): 連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した．該当論文では，問題そのものを直接解くのではなく，ある種のメタアルゴリズムを作るという方針をとった．グラフ同型性判定の古典的アルゴリズムとして，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
Format (IMT): application/pdf
Source: https://dspace.jaist.ac.jp/dspace/bitstream/10119/13677/1/25730003seika.pdf
https://dspace.jaist.ac.jp/dspace/bitstream/10119/13677/1/25730003seika.pdf
Access Restrictions: 限定公開
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 北陸先端科学技術大学院大学 : JAIST学術研究成果リポジトリ