论文摘要
组合优化问题是一门古老而又年轻的学科，在人们的生活中起着非常重要的作用，本文介绍了一类普通的组合优化问题—顶点覆盖。在我们以前的学习中碰到只是一种最小顶点覆盖，即在无向图G=（V，E）中选择尽可能少的点使其覆盖所有的边。在本文里我们将讨论另一类顶点覆盖—最大顶点覆盖，即在无向图G=（V，E）中，给定非负整数κ，κ≤|V|，在G中选择尼个点，使其覆盖的边数尽可能的多。鉴于最大顶点覆盖问题也是NP-hard的，除非P=NP，否则我们不可能在多项式时间内找到最优的算法。在这篇文章里，我们考虑一种特殊的图形—树，针对该图形设计一些近似算法，并分析其性能。本文共分为三个章节。第一章是引言部分，介绍了组合优化和算法的一些概念和基本知识。第二章主要介绍了我们比较熟悉的最小顶点覆盖问题，关于该问题有一些著名的结论和成果，我们给了一些介绍。第三章是本文的主要部分，我们详细讨论了树上的最大顶点覆盖问题，基于贪婪算法的思想，我们给出了两个算法，第一个算法我们称为Fully Greedy，其近似比为2，第二个算法我们称为Dynamic Greedy，其近似比为4/3。
论文目录
相关论文文献
- [1].一种增量式约简方法求解最小顶点覆盖问题[J]. 计算机应用研究 2018(12)
- [2].3度图的最小顶点覆盖问题的多项式时间算法[J]. 数学理论与应用 2014(03)
- [3].化学反应优化算法求解最小顶点覆盖问题[J]. 小型微型计算机系统 2015(02)
- [4].一种求解平面图的最小顶点覆盖算法[J]. 计算机系统应用 2010(09)
- [5].图的最小顶点覆盖问题的链置换模型[J]. 佳木斯大学学报(自然科学版) 2018(02)
- [6].奖励收集顶点覆盖问题的一个2-近似算法[J]. 北京化工大学学报(自然科学版) 2014(02)
- [7].树上限制性k-node multi-multiway cut 问题的近似算法[J]. 洛阳理工学院学报(自然科学版) 2020(03)
- [8].改进的最小顶点覆盖问题的贪婪算法[J]. 内蒙古师范大学学报(自然科学汉文版) 2012(02)
- [9].顶点覆盖问题线性内核算法[J]. 计算机研究与发展 2008(S1)
- [10].加权最小顶点覆盖的加权分治算法[J]. 小型微型计算机系统 2015(05)
- [11].最小顶点覆盖问题的加权分治算法[J]. 运筹与管理 2015(05)
- [12].最小顶点覆盖快速降阶算法[J]. 小型微型计算机系统 2008(07)
- [13].分层算法求解竞赛图上的最小弱顶点覆盖[J]. 北京化工大学学报(自然科学版) 2012(01)
- [14].Series-Parallel图上最小权顶点覆盖3-路问题的有效算法[J]. 北京化工大学学报(自然科学版) 2019(01)
- [15].图顶点覆盖问题决策神经网络模型[J]. 计算机学报 2009(08)
- [16].最少顶点覆盖问题的研究[J]. 中国新通信 2014(13)
- [17].DNA计算图的最小顶点覆盖问题[J]. 襄樊职业技术学院学报 2008(01)
- [18].一种混合化学反应优化算法求解最小顶点覆盖问题[J]. 计算机应用研究 2016(09)
- [19].次模函数近似算法求最小弱顶点覆盖[J]. 北京化工大学学报(自然科学版) 2011(01)
- [20].图的最小顶点覆盖的粘贴DNA计算模型[J]. 首都师范大学学报(自然科学版) 2013(01)
- [21].基于DNA步行者求解最小顶点覆盖问题的计算模型[J]. 广州大学学报(自然科学版) 2020(01)
- [22].单个飞机噪声事件最小顶点覆盖模型的机场噪声监测点分布方法[J]. 噪声与振动控制 2012(03)
- [23].基于DNA自组装模型解决图的最小顶点覆盖问题[J]. 安徽理工大学学报(自然科学版) 2015(03)
- [24].基于邻接矩阵与关联矩阵解决最大匹配等问题[J]. 贵阳学院学报(自然科学版) 2015(02)
- [25].最小顶点覆盖问题的竞争决策算法[J]. 计算机工程与应用 2011(01)
- [26].基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型[J]. 长春师范大学学报 2017(12)
- [27].三正则图上的P_3顶点覆盖问题[J]. 杭州电子科技大学学报(自然科学版) 2019(05)
- [28].基于混合优化算法的网络流量有效测量点选择[J]. 计算机应用研究 2009(04)
- [29].模糊环境下的最小权顶点覆盖问题[J]. 计算机应用研究 2012(01)
- [30].粘贴模型在两类特殊问题中的改进算法研究[J]. 计算机科学 2012(S3)