顶点覆盖问题的一种近似算法

摘要：

顶点覆盖问题就是对给定的一个无向图，找出图的最小顶点覆盖集。这个问题是一个NP-完全问题。通过对图论的原理进行分析和研究，提出了一种近似算法求顶点覆盖问题，该算法易于理解，获得了较好的实验结果，提高了算法的性能。

关键词： 顶点覆盖 近似算法 贪心算法 图论

作者: 王克俭 郭涛 陈晨

作者单位: 河北农业大学信息科学与技术学院 保定 071000

会议类型: 国内会议

会议名称: 全国第十五届离散数学学术研讨会

会议地点: 南京

会议语种:中文

页码: 80-82

在线出版日期: 2010-08-01（万方平台首次上网日期，不代表论文的发表时间）