摘要
最优顶点覆盖问题是6个基本的NP完全问题之一,无法在多项式时间内得到最优解,除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时,证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。
The Mininum Vertex Cover problem is one of the six ＂basic＂ NP-eomplete problem, it cannot be solved in polynomial time, unless N = NP. The algorithm of this paper solved vertex cover problem from another point of view. It improved the Greedy-Edge Approximation Mgorithm, proved and discussed that the approximation factor of the Improved Greedy-Edge Approximation Mgorithm containing the number of Single point Greedy-Edge and the number of Double point Greedy-Edge was not more than 2.
出处
《计算机应用》
CSCD
北大核心
2006年第1期149-151,共3页
journal of Computer Applications
关键词
顶点覆盖
近似算法
近似因子
单点贪心边
双点贪心边
贪心边
vertex cover
approximation algorithms
approximation factor
single point greedy-edge
double point greedyedge
greedy-edge
