Algorithms For Vertex Cover Problem

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at leastone vertex of the set. the minimum vertex cover (minvc) problem is to find the minimum sized vertexcover in a graph. minvc is a prominent combinatorial optimization problem with many applications,such as network security. cook introduced the problem and in later, he showed that the vertex coverproblem is np-hard. karp showed that finding the solution of minimal vertex cover problem in a graphis an np-complete problem. furthermore, it is np-hard to approximate mvc within any factor smallerthan 1.3606. in this work, we introduce study this problem and developed a new algorithm, called novc,for vertex cover problem that its complexity is nc/δ. where n is the number of vertices, c is the numberof vertices in the vertex cover and δ is the minimum degree of the graph. the running time is better thanthe algorithms being compared to.