文献

J-GLOBAL ID：202002256245400299   整理番号：20A1201422

対応h-colouringsの複雑性【JST・京大機械翻訳】

Complexity of correspondence H-colourings

著者 (2件)： Feder Tomas (268 Waverley Street, Palo Alto, CA 94301, USA) ,  Hell Pavol (School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada, V5A 1S6)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 281  ページ： 235-245  発行年： 2020年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 対応するホモモルフィズムは,対応する色(DP-彩色としても知られている)と同様に標準的なホモモルフィズムを一般化する。固定されたターゲットグラフHに対して,V(H)の一対の順列によりラベル付けされた各エッジを持つ入力グラフGがラベルに対応するHに対するホモモルフィズムを与えるかどうかを決定する問題を研究した。Hに対する同形写像はH-彩色と呼ばれる。そして,著者らは,対応するホモモルフィズムに対する類似の用語対応H-彩色を採用する。この問題の複雑さを固定グラフHの関数として分類した。それは,問題の各々が多項式時間可解性またはNP完全性であることを示した。ほとんどのグラフHはNP完全問題を生じるが,グラフHの興味ある事例があり,そのために,問題をガウス除去により多項式時間で解くことができる。また,類似の対応リスト同形問題の複雑性を分類し,また,両問題の二部分版の複雑さを分類した。Hが反射する場合について詳細な証明を行い,記録に対しては残りの証明をスケッチした。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 順列 ,  同形写像 ,  *発色 ,  準同形写像 ,  NP完全問題
準シソーラス用語： 決定可能性 ,  複雑性 ,  多項式時間 ,  NP完全性 , 【Automatic Indexing@JST】

著者キーワード (7件)： グラフ準同形写像 ,  H-カラーリング ,  対応彩色 ,  DPカラーリング ,  二分法 ,  NP完全性 ,  多項式アルゴリズム

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (1件)： 複雑性