文献

J-GLOBAL ID：201902269289742327   整理番号：19A1044442

調和的彩色:パラメータ化アルゴリズムと上界【JST・京大機械翻訳】

Harmonious coloring: Parameterized algorithms and upper bounds

著者 (5件)： Kolay Sudeshna (Eindhoven University of Technology, Netherlands) ,  Pandurangan Ragukumar (Rajalakshmi Engineering College, Sriperumbudur, Chennai, India) ,  Panolan Fahad (University of Bergen, Norway) ,  Raman Venkatesh (The Institute of Mathematical Science, HBNI, Chennai, India) ,  Tale Prafullkumar (The Institute of Mathematical Science, HBNI, Chennai, India)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 772  ページ： 132-142  発行年： 2019年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフの調和的な彩色は,頂点集合の部分への分割であり,各部分の中にエッジがなく,どの部分の間にもほとんどのエッジがある。最小調和彩色数の発見は,木や分割グラフのようなグラフの特殊クラスにおいてさえNP困難であることが知られている。調和着色のパラメータ化と正確な指数時間複雑性の研究を開始した。著者らは,既知の保証された限界とグラフの頂点カバー数により,解サイズによるような種々のパラメータ化を考察した。この問題は,解の大きさによってパラメータ化されると単純な二次カーネルを持つが,この問題はグラフの頂点カバーのサイズによってパラメータ化されるときに,問題が固定パラメータ追跡可能であるということである。これは,固定変数整数線形計画法の複数の事例に対する問題を低減することによって示される。また,n-kまたはΔ+1+k色がn頂点グラフGの調和的着色において十分であるかどうかを決定するのはW[1]困難であることを観測した。ここでΔはGの最大次数であり,kはパラメータである。正確な指数時間アルゴリズムに関して,著者らは,2NNO(1)アルゴリズムを開発して,ナイーブ2O(nlog n)アルゴリズム上で改善する分割グラフにおける最小調和着色を発見した。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 着色 ,  *パラメータ ,  NP困難 ,  *パラメタリゼーション ,  *アルゴリズム ,  *発色 ,  整数線形計画法
準シソーラス用語： 次数 ,  複雑性 ,  彩色数 ,  *上界 ,  パラメータ化アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (5件)： 調和した着色 ,  固定パラメータ追跡可能性 ,  頂点被覆 ,  上界 ,  分割グラフ

分類 (2件)： グラフ理論基礎  (IA02020S) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (4件)： 調和 ,  彩色 ,  パラメータ化アルゴリズム ,  上界