An Approximation Algorithm for the Minimum Vertex Cover Problem

详细信息    查看全文

• 作者：Jingrong Chen ; ^{chenjr@mail.lzjtu.cn" class="auth_mail" title="E-mail the corresponding author} ; Lei Kou ; Xiaochuan Cui
• 关键词：minimum vertex cover problem ; Dijkstra algorithm ; approximation algorithm ; time complexity
• 刊名：Procedia Engineering
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：137
• 期：Complete
• 页码：180-185
• 全文大小：159 K

文摘

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(n³⁾ 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.