An Approximation Algorithm for the Minimum Vertex Cover Problem

Abstract

The minimum vertex cover problem is a basic combinatorial optimization problem. Given an undirected graph the objective is to determine a subset of the vertices which covers all edges such that the number of the vertices in the subset is minimized. In the paper, based on Dijkstra algorithm, an approximation algorithm is obtained for the minimum vertex cover problem. In the process of getting a vertex cover, the maximum value of shortest paths is considered as a standard, and some criteria are defined. The time complex of the Algorithm is O(n3) where n is the number of vertices in a graph. In the end, an example is given to illustrate the process and the validity of the Algorithm.