文献

J-GLOBAL ID：201102200783347899   整理番号：11A0160350

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

Graph Classes and Subgraph Isomorphism

著者 (4件)： 斎藤寿樹 (JST-ERATO) ,  大舘陽太 (東北大) ,  来嶋秀治 (九大) ,  宇野毅明 (国立情報学研)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2010  号： 4  ページ： ROMBUNNO.AL-132,5  発行年： 2010年12月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 部分グラフ同型性判定問題は2つのグラフGとHが与えられたとき,GをHに埋め込めるかどうかを判定する問題である。この問題は,ハミルトンパス問題や最大クリーク問題など多くのNP-完全な問題を含んでいるため,一般のグラフ上だけでなく,二つのグラフを連結な平面グラフに制限してもNP-完全である。本論文では,ハミルトンパス問題や最大クリーク問題,同型性判定問題を多項式時間で解くことができるグラフクラス上の部分グラフ同型性判定問題を扱う。具体的には,真区間グラフ(Proper interval graphs),準閾値グラフ(Trivially perfect graphs),二部置換グラフ(Bipartite permutation graphs)上の部分グラフ同型性判定問題がNP-完全であることを示す。また,これらのグラフクラスの部分クラスである補鎖グラフ(Co-chain graphs),鎖グラフ(Chain graphs),閾値グラフ(Threshold graphs)に対し,多項式時間アルゴリズムを提案する。(著者抄録)

シソーラス用語： *部分グラフ ,  埋込み【挿入】 ,  *Hamilton路 ,  *最大化問題 ,  アルゴリズム ,  計算量 ,  *NP完全問題 ,  グラフ ,  同形写像
準シソーラス用語： 最大クリーク問題 ,  同型性判定問題 ,  多項式時間アルゴリズム ,  閾値グラフ

分類 (3件)： グラフ理論基礎  (IA02020S) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： グラフ ,  クラス ,  グラフ同型