グラフクラスと部分グラフ同型性

• Item type: SIG Technical Reports(1)
• 公開日: 2010-11-12
• タイトル: グラフクラスと部分グラフ同型性
• タイトル / 言語: en
• タイトル: Graph Classes and Subgraph Isomorphism
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 科学技術振興機構ERATO湊離散構造処理系プロジェクト
• 著者所属: 東北大学情報科学研究科
• 著者所属: 九州大学システム情報科学研究院
• 著者所属: 国立情報学研究所情報学プリンシプル研究系
• 著者所属(英): en
• 著者所属(英): JST, ERATO, MINATO Discrete Structure Manipulation System Project
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者名: 斎藤, 寿樹; 大舘, 陽太; 来嶋, 秀治; 宇野, 毅明
• 著者名(英): Toshiki, Saitoh; Yota, Otachi; Shuji, Kijima; Takeaki, Uno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 部分グラフ同型性判定問題は 2 つのグラフ G と H が与えられたとき，G を H に埋め込めるかどうかを判定する問題である．この問題は，ハミルトンパス問題や最大クリーク問題など多くの NP-完全な問題を含んでいるため，一般のグラフ上だけでなく，二つのグラフを連結な平面グラフに制限しても NP-完全である．本論文では，ハミルトンパス問題や最大クリーク問題，同型性判定問題を多項式時間で解くことができるグラフクラス上の部分グラフ同型性判定問題を扱う．具体的には，真区間グラフ (Proper interval graphs)，準閾値グラフ (Trivially perfect graphs)，二部置換グラフ (Bipartite permutation graphs) 上の部分グラフ同型性判定問題が NP-完全であることを示す．また，これらのグラフクラスの部分クラスである補鎖グラフ (Co-chain graphs)，鎖グラフ (Chain graphs)，閾値グラフ (Threshold graphs) に対し，多項式時間アルゴリズムを提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The subgraph isomorphism problem is to determine whether a graph isisomorphic to a subgraph of another graph. Since it includes the Hamiltonian path problem, the subgraph isomorphism problem is NP-complete even if the input graphs are connected plannar graphs. In this paper, we deal with proper interval graphs, trivially perfect graphs, and bipartite permutation graphs, and their subclasses. We know that on these graphs Hamiltonian path, maximum clique, and isomorphism problems can be solved in polynomial time. We show that the subgraph isomorpshim is NP-complete even when both of given graphs are connected proper interval graphs, trivially perfect graphs, and bipartite permutation graphs. Then, we propose polynomial time algorithms for the subgraph isomorphism problem on co-chain graphs, chain graphs, and threshold graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2010-AL-132, 号 5, p. 1-8, 発行日 2010-11-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会