福州大学学报（自然科学版）2001，Vol.29Issue(1)：8-11,4.
顶点覆盖问题的贪心算法的设计与分析
Design and analysis of vertex covered problem by greedy algorithm
摘要
Abstract
As the relative rate η≤2 between such approximate solution andexact solution, this paper introduces another greedy algorithm to solve the problem，and proves the relative rate η≤H(d)， H(d)= ∑1/j (j=(1， 2， ……， d)， where d is the maximal degree of vertex in the graph. Therefore，greedy algorithm has improved the accuracy of solution evidently while d≤3.关键词
顶点覆盖/贪心算法/NP—困难分类
信息技术与安全科学引用本文复制引用
姚朝灼..顶点覆盖问题的贪心算法的设计与分析[J].福州大学学报（自然科学版）,2001,29(1):8-11,4.
