最优顶点覆盖的贪心边近似算法

Greedy-Edge Approximation Algorithm with the Optimal Vertex-cover

提出了一种新的贪心边近似算法,能保证性能比不大于2的同时比传统的选任意边算法有更优的解,在可验证(能得到最优覆盖点数)时,统计数据表明贪心边算法非常有效,是一个集合了传统的任选一边近似算法和选择度数最大点的贪心算法两者优点的新算法.

A new greedy-edge approximation algorithm is put forward in this paper. The property factor is not bigger than 2. At the same time,the new method has much better solutions than the traditional method. In testing the optimal cover point number, the statistic data indicate that the greedy-edge algorithm is very effective. It is a new method which combine the advantages of the traditional approximation algorithm with arbitrary edge and the greedy-edge algorithm with the biggest selected point.