最小权点覆盖问题的一个近似算法

An Approximation Algorithm for Minimum Weighted Vertex Cover Problem

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.

Based on the Dijkasta algorithm, this paper gives an approximation algorithm for the minimum weighted vertex cover problem. First, let an arbitrary vertex be the initial point, and the allowed set and some definitions axe given. Then, by using he Dijkasta algorithm to get the shortest path from the initial point to each vertex in the allowed set, and obtain the vertex cover in accordance with certain principles. In the end, an example is given to illustrate the rationality and effectiveness of the algorithm.