A Simple NOVCA: Near Optimal Vertex Cover Algorithm

被引：8

作者：

Gajurel, Sanjaya ^{[1
]}

Bielefeld, Roger ^{[1
]}

机构：

[1] Case Western Reserve Univ, Cleveland, OH 44106 USA

来源：

PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE, ICCS 2012 | 2012年 / 9卷

关键词：

Vertex Cover Problem; Combinatorial Problem; NP-Complete Problem; Approximation Algorithm;

D O I：

10.1016/j.procs.2012.04.080

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper describes an extremely fast polynomial time algorithm, the Near Optimal Vertex Cover Algorithm (NOVCA) that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA constructs the vertex cover by repeatedly adding, at each step, all vertices adjacent to the vertex of minimal degree; in the case of a tie, it selects the one having the maximum sum of degrees of its neighbors. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any other available vertex cover algorithms.

引用

页码：747 / 753

页数：7

共 13 条

[1] Crown structures for vertex cover kernelization [J].