文献

J-GLOBAL ID：201702279984265234   整理番号：17A0565969

最も低いエッジ支配集合に対する正確アルゴリズム

An Exact Algorithm for Lowest Edge Dominating Set

著者 (2件)： IWAIDE Ken (Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University) ,  NAGAMOCHI Hiroshi (Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E100.D  号： 3  ページ： 414-421(J-STAGE)  発行年： 2017年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 無向グラフGが与えられた場合,エッジ支配集合はFにない各エッジがFのあるいくつかのエッジに隣接するようなエッジの部分集合Fであり,エッジ支配集合の最小サイズを計算することはNP困難であることが知られている。あらゆるエッジ支配集合のサイズは,Gにおける整合の最大サイズμ(G)の少なくとも半分であるため,与えられたグラフGがサイズμ(G)/2のエッジ支配集合をもつか否かの試験問題を研究した。本論文では,この問題がNP完全であることの証明と,本問題に対するO^*(2.080I^μ(G)/2)タイムおよび多項式空間アルゴリズムの設計について報告した。(翻訳著者抄録)

シソーラス用語： *端部 ,  *無向グラフ ,  NP完全問題 ,  多項式 ,  *集合 ,  設計 ,  アルゴリズム設計
準シソーラス用語： *支配集合

著者キーワード (5件)： graph theory ,  edge dominating set ,  algorithm ,  NP-completeness ,  fixed parameter tractable

分類 (1件)： 計算理論  (JB02000A)

引用文献 (16件)：

• [1] D. Binkele-Raible and H. Fernau, “Parameterized Measure & Conquer for Problems with No Small Kernels,” Algorithmica, vol.64, no.1, pp.189-212, 2012.
• [2] H. Fernau, “Edge Dominating Set: Efficient Enumeration-Based Exact Algorithms,” In H. Bodlaender, M. Langston (eds.), IWPEC 2006. LNCS 4169, Springer-Verlag, pp.142-153, 2006.
• [3] F.V. Fomin, S. Gaspers, S. Saurabh, and A.A. Stepanov, “On Two Techniques of Combining Branching and Treewidth,” Algorithmica, vol.54, no.2, pp.181-207, 2009.
• [4] T. Fujito and H. Nagamochi, “A 2-Approximation Algorithm for the Minimum Weight Edge Dominating Set Problem,” Discrete Applied Mathematics, vol.118, no.3, pp.199-207, 2002.
• [5] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to The Theory of NP-Completeness, Freeman, San Francisco, 1979.

タイトルに関連する用語 (3件)： エッジ ,  支配集合 ,  アルゴリズム