文献

J-GLOBAL ID：201702268536194698   整理番号：17A0539059

頂点被覆問題のサイズ-tサイクル被覆問題へ拡張

Extension of the Vertex Cover Problem to the Size-t Cycle Cover Problems

著者 (2件)： DASHDEMBEREL Batchunag (Tokyo Inst. Technol., Tokyo) ,  WATANABE Osamu (Tokyo Inst. Technol., Tokyo)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 116  号： 503(COMP2016 50-55)  ページ： 11-18  発行年： 2017年02月28日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： グラフ頂点被覆(略称VC)問題の拡張を考える。グラフの全ての辺に対して,その辺上の頂点を1つ以上を含む頂点部分集合が(辺の)頂点被覆(略称,VC)である。この概念を拡張し,パラメータtに対し,「サイズ-tのサイクルの頂点被覆集合」(略称,VCC_t)を考える。頂点数tのサイクル全てに対して,そのサイクル上の頂点を1つ以上を含む頂点部分集合である。本論文では,与えられたグラフに対し,頂点数最小のVCC_tを求める問題(略称,VCC_t問題)を考え,任意のt≧2に対し,この問題のNP-困難性を示す。さらに,とくにt=4の場合に,木幅がk以下のグラフ対してVCC₄問題を,(2^k・√<span style=text-decoration:overline>1</span><span style=text-decoration:overline>2</span>^A:A=k²・k^O(1)・+k^A:A=O(k³)・O(n)-時間で解くアルゴリズムを提案する。(著者抄録)

シソーラス用語： *被覆問題 ,  幅 ,  *木【グラフ】 ,  *計算機アルゴリズム ,  部分集合 ,  *頂点 ,  端部 ,  NP困難 ,  定義 ,  定理証明 ,  サイクル ,  パラメータ
準シソーラス用語： 頂点被覆問題 ,  有界木幅 ,  FPTアルゴリズム ,  固定パラメータトラクタビリティ ,  サイクル被覆

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

引用文献 (12件)：

• N. Robertson and P.D. Seymour, Graph minors. III. Planar tree-width, Journal of Combinatorial Theory, Series B, Volume 36, Issue 1, Pages 49-64, 1984.
• H.L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, SIAM Journal of Computing 25, 1305-1317, 1996.
• J. Tu, L. Wu, J. Yuan and L. Cui, On the vertex cover P₃ problem parameterized by treewidth, Journal of Combinatorial Optimization, Volume 31 Issue 2, 2016. doi:10.1007/s10878-016-9999-6.
• Z. Bai, J. Tu, and Y. Shi, An improved algorithm for the vertex cover P₃ problem on graphs of bounded treewidth, ArXiv e-prints 1603.09448, March, 2016.
• M. Cygan, F.V. Fomin, ?. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms, Springer 2015.

タイトルに関連する用語 (5件)： 頂点 ,  被覆問題 ,  サイズ ,  サイクル ,  拡張