文献

J-GLOBAL ID：201702284785254545   整理番号：17A1548373

有界木幅のグラフにおける禁止部分グラフを打つ【Powered by NICT】

Hitting forbidden subgraphs in graphs of bounded treewidth

著者 (4件)： Cygan Marek (Institute of Informatics, University of Warsaw, Poland) ,  Marx Daniel (Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Hungary) ,  Pilipczuk Marcin (Department of Computer Science, University of Warwick, United Kingdom) ,  Pilipczuk Michal (Institute of Informatics, University of Warsaw, Poland)
資料名： Information and Computation  (Information and Computation)
巻： 256  ページ： 62-82  発行年： 2017年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 固定パターングラフと入力グラフGを与えられたが,タスクはHに同形Gのすべての部分グラフに衝突する最小サイズの集合X⊆V(G)を見出すことである打撃ここでは,一般的なヒット問題Hサブグラフの複雑さを研究した。問題の多彩な変異体では,Gの各頂点はV(H)からいくつかの色とprecoloredであり,色マッチングを用いたH部分グラフのみを必要とする。標準法は各固定H,問題であるGのツリー幅によってパラメータ化された固定パラメータ・トラクタブルであることを示した。が,木幅に依存する厳密に実行時間かは明らかでない。カラフル変異体については,筆者らはもしGの木幅における走行時間の依存性はμ(H),H.における最小頂点セパレータの最大サイズにより支配されることを示した上限と下限をマッチング実証した。すなわち,筆者らは全ての固定Hを示し,木幅のグラフ,色彩豊かな問題は時間二零(tμ(H))V(G)で解くことができるが,時間二零(tμ(H))V(G)O(1),を仮定して指数時間仮説(ETH)では解が得られないことを示した。さらに,色の非存在下では,Hサブグラフ打撃のパラメータ付き計算量景観は非常に富むことを示すいくつかの予備的結果を与えた。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *部分グラフ ,  計算量 ,  パラメタリゼーション ,  マッチング ,  *グラフ ,  色相 ,  色合せ ,  走行時間
準シソーラス用語： 実行時間 ,  *木幅 , 【Automatic Indexing@JST】

著者キーワード (3件)： 固定パラメータ実行可能性 ,  木幅 ,  禁止部分グラフ

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

タイトルに関連する用語 (4件)： 有界木幅 ,  グラフ ,  禁止 ,  部分グラフ