New Complexity Bound of Greed Algorithm of Vertex Cover for Low-degree Graph

摘要：

Vertex cover of a graph is a set of vertices which can cover all edges and k vertex cover problem is to find a vertex cover whose cardinality is no more than k. In this paper, firstly we prove a new property about simple cycles of graph, then we apply this property to analyze a simple greed algorithm for k vertex cover problem of graph whose maximum vertex degree is no more than 3.By analysis weshow that it has a lower complexity O(1.1949k)using the newproperty instead of O(1.4656k) without using the new property. To the best of our knowledge, it is the simplest algorithm with such a low complexity to deal with the problem. The new complexity is comparable with the best publishedcomplexity bound O(1.1849k) which use a more complicate algorithm. So through our analysis, it shows that the greed algorithm is practical and that the new property about simple cycle of graph is a great tool for analyzing vertex cover problem and other graph algorithms.

关键词： vertex cover complexity real-cycle

作者: Weiya Yue Weiwei Cao Hongwei Yue

作者单位: Computer Science Department, University of Cincinnati, Cincinnati Ohio, US 45220 State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijin Information College, Zhongkai University of Agriculture and Engineering, Guangzhou 510225 Guangdong

会议类型: 国际会议

会议名称: 2010 International Conference on Future Information Technology(2010年未来信息技术国际会议 ICFIT 2010)

会议地点: 长沙

会议语种:英文

页码: 77-82

在线出版日期: 2010-12-14（万方平台首次上网日期，不代表论文的发表时间）