求一般图的最小顶点覆盖集问题的混合贪婪算法

吕健康; 张国基

首页> 中文期刊> 《科学技术与工程》 >求一般图的最小顶点覆盖集问题的混合贪婪算法

求一般图的最小顶点覆盖集问题的混合贪婪算法

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.

著录项

来源
《科学技术与工程》 |2010年第20期|4891-4895|共5页
作者
吕健康; 张国基;
展开▼
作者单位

华南理工大学理学院,广州,510000;

华南理工大学理学院,广州,510000;

展开▼
原文格式 PDF
正文语种 chi
中图分类图论;
关键词
最小顶点覆盖集; 复杂度分析; 混合贪婪算法;

相似文献

中文文献
外文文献
专利

1. 改进的最小顶点覆盖问题的贪婪算法 [J] . 张楠 ,张升 . 内蒙古师范大学学报（自然科学汉文版） . 2012,第002期
2. 求图的最小顶点覆盖集的一个近似算法 [J] . 闫兴篡 ,殷建平 ,蔡志平 . 哈尔滨工业大学学报 . 2008,第007期
3. 一种混合化学反应优化算法求解最小顶点覆盖问题 [J] . 郑光勇 ,徐雨明 ,李肯立 . 计算机应用研究 . 2016,第009期
4. 超图的连通边控制集问题一个贪婪算法 [J] . 苏亚娟 . 现代商贸工业 . 2012,第018期
5. 基于时间满意的集覆盖问题及若干贪婪算法应用研究 [J] . 马云峰 ,刘勇 ,杨超 . 武汉科技大学学报（自然科学版） . 2006,第006期
6. 一种求解图最小顶点覆盖问题的混合遗传算法 [C] . Zhou Benda ,周本达 ,Chen Minghua . 第三届中国智能计算大会 . 2009
7. 基于贪婪算法的容错外连通控制集问题研究 [A] . 王晓芝 . 2020

求一般图的最小顶点覆盖集问题的混合贪婪算法

摘要

著录项

相似文献

相关主题

期刊订阅