文献

J-GLOBAL ID：201902281079344417   整理番号：19A1195206

有界木幅を持つグラフ上のHフリー彩色【JST・京大機械翻訳】

H-Free Coloring on Graphs with Bounded Tree-Width

著者 (3件)： Aravind N. R. (Department of Computer Science and Engineering, IIT Hyderabad, Hyderabad, India) ,  Kalyanasundaram Subrahmanyam (Department of Computer Science and Engineering, IIT Hyderabad, Hyderabad, India) ,  Kare Anjeneya Swami (School of Computer and Information Sciences, University of Hyderabad, Hyderabad, India)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11394  ページ： 231-244  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Hは固定されていない有向グラフである。無指向入力グラフGの頂点彩色は,色クラスのいずれも,誘導されたサブグラフとしてHを含まない場合には,[数式:原文を参照]フリーカラーリングであると言われている。Gの[数式:原文を参照]-フリー染色番号は,Gの[数式:原文を参照]-フリーカラーリングに必要な色の最小数である。この問題はNP完全であり,一次二次論理(MSOL)において表現可能である。Courcelleの定理と共にMSOL定式化は,有界木幅を持つグラフ上の線形時間可解性を意味する。このアプローチは,[数式:原文を参照]がMSOL式の長さである,実行時間[数式:原文を参照]を有するアルゴリズムを生み出す。tはグラフの木幅であり,nはグラフの頂点の数である。[数式:原文を参照]に対する[数式:原文を参照]の依存性は,指数関数の塔と同様に悪い。本論文では,Gの木幅によりパラメータ化された与えられたグラフGの[数式:原文を参照]-自由染色数を計算するために,明示的組合せFPTアルゴリズムを提供した。この技術は,HがGの色クラスにおいてサブグラフ(必ずしも誘導されない)として禁止されるとき,FPTアルゴリズムを提供するためにも使用される。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 定式化 ,  染色 ,  指数関数 ,  *発色 ,  パラメタリゼーション ,  線形性 ,  有向グラフ ,  塔状構造物 ,  着色 ,  *グラフ ,  部分グラフ ,  アルゴリズム
準シソーラス用語： *木幅 ,  決定可能性 ,  *有界木幅 , 【Automatic Indexing@JST】

分類 (1件)： 分子・遺伝情報処理  (JE15040B)

タイトルに関連する用語 (3件)： 有界木幅 ,  グラフ ,  彩色