文献

J-GLOBAL ID：201802237709006586   整理番号：18A0328158

2禁止誘導部分グラフにより特性化されたグラフ・クラスのためのグラフ同形【Powered by NICT】

Graph isomorphism for graph classes characterized by two forbidden induced subgraphs

著者 (2件)： Kratsch Stefan (Technical University Berlin, Ernst-Reuter-Platz 7, 10587 Berlin, Germany) ,  Schweitzer Pascal (RWTH Aachen University, Ahornstr. 55, 52074 Aachen, Germany)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 216  号： P1  ページ： 240-253  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 有限数禁止誘導部分グラフのによって特性化された二禁止部分グラフの1例に焦点を当てているグラフクラス上でのグラフ同形写像問題の複雑さを研究した。硬度結果を示し,そのようなグラフクラスの構造解析のための技術を開発した。二禁止部分グラフの1例に適用し,主な結果:多くの場合が有限全て同形完全多項式時間可解なグラフクラスに二分法を得るために,禁止グラフもクリーク,パン,またはこれらのグラフの補体である。さらに残留開症例を低減(グラフ同形に関して)パンを禁止しただけで大きさ三のクリークを禁止に等価であることを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *キャラクタリゼーション ,  *部分グラフ ,  硬度 ,  補体 ,  構造解析 ,  *グラフ
準シソーラス用語： 多項式時間 ,  グラフ同型 , 【Automatic Indexing@JST】

著者キーワード (3件)： グラフ同形 ,  グラフクラス ,  禁止誘導部分グラフ

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (6件)： 禁止 ,  誘導 ,  部分グラフ ,  特性化 ,  グラフ ,  クラス