Complexity and algorithms for the connected vertex cover problem in 4-regular graphs

详细信息    查看全文

• 作者：Yuchao Li ^{liyu_chao@126.com} ; Zishen Yang ^{yangzishen@sina.com} ; Wei Wang ; ^{wang_weiw@163.com}
• 关键词：Connected vertex cover problem ; Approximation algorithm ; 4-regular graph
• 刊名：Applied Mathematics and Computation
• 出版年：2017
• 出版时间：15 May 2017
• 年：2017
• 卷：301
• 期：Complete
• 页码：107-114
• 全文大小：728 K
• 卷排序：301

文摘

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 32 and 43+O(1n), respectively.