顶点覆盖问题的贪心算法的设计与分析  

Design and analysis of vertex covered problem by greedy algorithm

作　　者：姚朝灼[1] 

机构地区：[1]福州大学计算机科学与技术系,福建福州350002

出　　处：《福州大学学报（自然科学版）》2001年第1期8-11,共4页Journal of Fuzhou University(Natural Science Edition)

摘　　要：设计了解顶点覆盖问题的贪心算法 ,并证明其相对比率 η≤H(d) ,d为图中最大的顶点度数 ,H(d) =∑1/ j(j =1,2 ,…… ,d) .当d ≤ 3时 ,解的精确度有明显改善 .As the relative rate η≤2 between such approximate solution and exact 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-困难 相对比率 顶点度数 无向图 时间分析 误差分析 数据结构 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O157.5[自动化与计算机技术—计算机科学与技术]