| 求一般图的最小顶点覆盖集问题的混合贪婪算法 |
| |
| 引用本文： | 吕健康. 求一般图的最小顶点覆盖集问题的混合贪婪算法[J]. 科学技术与工程, 2010, 10(20) |
| |
| 作者姓名： | 吕健康 |
| |
| 作者单位： | 华南理工大学理学院,广州,510000 |
| |
| 摘 要： | 现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.
|
| 关 键 词： | 最小顶点覆盖集 复杂度分析 混合贪婪算法 |
| 收稿时间： | 2010-04-20 |
| 修稿时间： | 2010-04-20 |
A new mixed greedy algorithm for solving minimum vertex cover set problems |
| |
| LV Jiankang. A new mixed greedy algorithm for solving minimum vertex cover set problems[J]. Science Technology and Engineering, 2010, 10(20) |
| |
| Authors: | LV Jiankang |
| |
| Affiliation: | L(U) Jian-kang,ZHANG Guo-ji |
| |
| Abstract: | |
| |
| Keywords: | words:minimum vertex cover problem complexity analysis mixed greedy algorithm |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《科学技术与工程》浏览原始摘要信息 |
|
点击此处可从《科学技术与工程》下载全文 |
|
