%0 Journal Article
%T Improved greedy-edge approximation algorithm of the optimal vertex-cover<br>改进的最优顶点覆盖贪心边近似算法
%A YANG Jie
%A <br>杨杰
%J 计算机应用
%D 2006
%I 
%X The Mininum Vertex Cover problem is one of the six "basic" NP-complete 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 Algorithm,proved and discussed that the approximation factor of the Improved Greedy-Edge Approximation Algorithm containing the number of Single point Greedy-Edge and the number of Double point Greedy-Edge was not more than 2.
%K vertex cover
%K approximation algorithms
%K approximation factor
%K single point greedy-edge
%K double point greedyedge
%K greedy-edge<br>顶点覆盖
%K 近似算法
%K 近似因子
%K 单点贪心边
%K 双点贪心边
%K 贪心边
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=831E194C147C78FAAFCC50BC7ADD1732&aid=B60A7FACBF026272&yid=37904DC365DD7266&vid=96C778EE049EE47D&iid=CA4FD0336C81A37A&sid=EB552E4CFC85690B&eid=7ACC6238C6DFEBD4&journal_id=1001-9081&journal_name=计算机应用&referenced_num=2&reference_num=12