文献

J-GLOBAL ID：201802270459147791   整理番号：18A0353099

最大内部スパンニング木のためのパラメータ化および近似アルゴリズムのためのより深い局所探索【Powered by NICT】

Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

著者 (5件)： Li Wenjun (School of Information Science and Engineering, Central South University, Changsha, China) ,  Li Wenjun (School of Computer and Communication Engineering, Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation, Changsha University of Science and Technology, Changsha, China) ,  Cao Yixin (Department of Computing, Hong Kong Polytechnic University, Hong Kong, China) ,  Chen Jianer (Department of Computer Science and Engineering, Texas A&M University, College Station, TX, United States) ,  Wang Jianxin (School of Information Science and Engineering, Central South University, Changsha, China)
資料名： Information and Computation  (Information and Computation)
巻： 252  ページ： 187-200  発行年： 2017年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最大内部スパンニング木問題をグラフのすべてのスパンニング木の間の内部頂点の最大数を持つことを与えられたグラフのスパンニング木を求める。パラメータ化版では,グラフが少なくともk個の内部頂点を有したスパンニング木を持つかどうかに興味を持った。Fominら(2013)は非常に巧妙な還元則を工夫し,この法則の簡単な応用である3Kバーテックスカーネルを得るために十分であることを示し,O~*(8~ k)-時間パラメータ化されたアルゴリズムを意味している。深さ2局所探索を用いて,KnauerとSpoerhase(2015)は最適化版(5/3)-近似アルゴリズムを開発した。より深い局所探索を試みた:得られたスパンニング木に関する徹底的な組合せ解析を行い,それらのアルゴリズム的結果を調べた。深さ局所探索によって得られたスパンニング木から,容易に還元可能な構造を見出し,Fominらの還元則を適用することができることを観測した。これは2k頂点の改善されたカーネルを与え,副産物として,決定論的アルゴリズムが時間的に走行O~*(4~ k)。を深さ5局所探索によって得られたスパンニング木を考慮して行くも深かった。このスパンニング木の内部点の数は,スパンニング木は,問題のための比1.5を持つ改良型近似アルゴリズムを届けることとなる最大数の少なくとも2/3であることを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *パラメタリゼーション ,  組合せ論 ,  *アルゴリズム ,  グラフ ,  *近傍探索法 ,  走行 ,  最適化 ,  *スパンニング木
準シソーラス用語： 決定論 ,  *近似アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (3件)： 最大内部スパンニング木 ,  パラメータ化された計算 ,  局所探索

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： スパンニング木 ,  パラメータ化 ,  近似アルゴリズム ,  局所探索