Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
复制标题
4-正则图中连通顶点覆盖问题的复杂度和算法
DOI：
10.1016/j.amc.2016.12.004
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Wei Wang
中科院分区：
文献类型：
--
作者：
Yuchao Li;Zishen Yang;Wei Wang
在连通顶点覆盖（CVC）问题中，我们给定一个连通图 G，并要求找到一个具有最小基数的顶点覆盖集 C，使得导出子图 G [C] 是连通的。在本文中，我们将注意力集中在 4-正则图中的 CVC 问题。我们证明了 CVC 问题对于 4-正则图仍然是 NP 困难的，并给出了该问题的下界。此外，我们针对CVC问题提出了两种近似算法，近似率分别为3 2 和4 3+ O (1 n)。
In the connected vertex cover (CVC) problem, we are given a connected graph G and required to find a vertex cover set C with minimum cardinality such that the induced subgraph G [C] is connected. In this paper, we restrict our attention to the CVC problem in 4-regular graphs. We proved that the CVC problem is still NP-hard for 4-regular graphs and gave a lower bound for the problem. Moreover, we proposed two approximation algorithms for CVC problem with approximation ratio 3 2 and 4 3+ O (1 n), respectively.
连通顶点覆盖和树覆盖的 2 近似 NC 算法
DOI：
--
发表时间：
2004
期刊：
Information Processing Letters 90
影响因子：
--
作者：
Fujito;T.;Doi;T.
通讯作者：
T.