4-正则图上的最小连通顶点覆盖问题

The Minimum Connected Vertex Cover Problem in 4-regular Graphs

任给一个4-正则图,研究如何寻找4-正则图顶点数目最少的顶点覆盖问题,使其导出子图是一个连通图。已研究证明该问题是NP-难的且存在最坏情况界不超过4/3+O(1/n)的近似算法,其中n为4-正则图的顶点数。在此基础上,提出该算法的一个改进分析,使其最坏情况界中的O(1/n)项得以舍去。

Given a 4-regular graph,it aims to find a vertex cover with the minimum number of vertices provided that the induced graph of the vertex cover is connected.It has been shown to be NP-hard and admits an approximation algorithm with worst-case ratio no more than 4/3+O(1/n),where n is the number of vertices of the 4-regular graph.This paper provides an improved algorithm with a tighter worst-case ratio,where the additive term O(1/n)could be removed.