导读:本文包含了最小顶点覆盖问题论文开题报告文献综述及选题提纲参考文献，主要关键词:Series-Parallel图,顶点覆盖k-路问题,有效算法,动态规划
最小顶点覆盖问题论文文献综述
张文杰,涂建华[1]（2019）在《Series-Parallel图上最小权顶点覆盖3-路问题的有效算法》一文中研究指出研究了Series-Parallel图上的顶点覆盖3-路问题,利用动态规划思想,给出一个能在多项式时间内完成的有效算法,该算法的运行时间为O(|V|)。(本文来源于《北京化工大学学报(自然科学版)》期刊2019年01期）
张春露,殷志祥[2]（2018）在《图的最小顶点覆盖问题的链置换模型》一文中研究指出针对DNA计算解决最小顶点覆盖覆盖问题,采用对空解的数据池进行解的删除操作,找出解的补集,重而获得问题的最优解。在链置换的基础上,代替酶的作用,提高了实验的效率,节省时间,此算法独特新颖,简单可靠。(本文来源于《佳木斯大学学报(自然科学版)》期刊2018年02期）
巩成艳,殷志祥,赵鑫月[3]（2017）在《基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型》一文中研究指出DNA自组装技术为DNA计算的发展带来了一些新的启发。目前,解决各种NP完全问题的方法有多种多样的计算模型,其中有些是非常有用的,可以解决复杂的NP完全问题。在本文中,在自组装纳米颗粒探针的基础上,介绍了关于最小顶点覆盖问题的一种新的DNA计算模型。将给定问题的变量0或1所有可能的组合,编码在自组装纳米探针的识别区,通过靶序列的杂交来判断其可行解。相对于传统的DNA计算模型,该模型具有方便、灵敏、稳定性高的优点。(本文来源于《长春师范大学学报》期刊2017年12期）
占善华,谢小军[4]（2018）在《一种增量式约简方法求解最小顶点覆盖问题》一文中研究指出最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间。实验结果表明了该算法的可行性和有效性。(本文来源于《计算机应用研究》期刊2018年12期）
郭洪敏[5]（2016）在《最小顶点覆盖问题的几种DNA算法研究》一文中研究指出传统的计算机由于其自身存储量和计算能力的有限,已经不能满足日益发展的科学形势。1994年,Adleman探索性的将现代生物技术与DNA操作技术结合起来,成功解决了具有七个节点的有向赋权图的哈密尔顿路径问题(Hamilton path problem),从此打开了生物计算的大门,让DNA分子作为一种新型的计算机硬件成为可能。而DNA分子由于具有传统计算机无法比拟的海量存储量和高度的计算并行性,使得其在密码学,数学,计算机等领域得到了广泛的青睐。本文将具体阐述DNA计算的研究背景、DNA分子结构、DNA分子操作过程等基本理论,并且对DNA分子操作过程中的初始编码问题进行了具体的分析,包括初始编码问题的基本概念,初始编码的约束条件和具体的编码方法；还将简单介绍一些常用的DNA计算模型(剪接模型、分子信标、质粒DNA模型以及DNA自组装模型等)的基本操作原理及优缺点。此外,本文将具体介绍最小顶点覆盖问题、可满足性问题、线性规划问题的基本概念,并巧妙的将复杂的最小顶点覆盖表转化为形式简便的0-1规划问题和可满足性问题,这也是本文的创新之处。并在此基础上,结合DNA自组装模型、质粒DNA模型,给出基本算法和具体生物操作过程,具有一定研究意义。(本文来源于《安徽理工大学》期刊2016-06-01）
段侠[6]（2016）在《点赋权二部图上最大边装填问题和最小顶点覆盖问题的相关性及其算法研究》一文中研究指出给定一个无向图,一个边的子集称为匹配,如果里面的任意两条边都没有共同的交点；一个顶点的子集称为顶点覆盖,如果图中每一条边的两个端点中的至少一个在该顶点子集内。经典的最大匹配问题要求图中包含边数最多的匹配,而经典的顶点覆盖问题要求图中包含顶点数最少的顶点覆盖。匹配与顶点覆盖问题是组合最优化研究的中心问题。在计算复杂性方面,匹配可认为是类问题的典型代表,顶点覆盖问题可认为是难问题的典型代表。对匹配与顶点覆盖问题的持续和深入研究推动了学科的发展,丰富了算法理论和技巧,揭示了深刻的数学关系。Kǒnig(1931)找到了让这两个问题相互联系的图论结构：二部图。经典的Kǒnig定理断言：在二部图中,最大的匹配包含的边数等于最小的顶点覆盖包含的顶点数。20世纪以来离散数学的发展见证了Kǒnig定理的深刻性。很多推动学科发展的着名定理都和Kǒnig定理等价,它们包括：代数学中的P. Hall定理,偏序集上的Dilworth定理,图论中的Menger定理,网络流的最大流最小割定理等等。本文研究点赋权二部图上的边装填与顶点覆盖问题,关注它们的关系及其算法研究。给定一个无向图,每个顶点上有一个正整数权重,一个边的子集(边允许重复)称为一个边装填,如果图中每个顶点与中的边相关联的数目不超过该点的权重；一个顶点的子集称为顶点覆盖,如果图中每一条边都与相交。最大边装填问题要求图中包含边数最多的边装填,而最小顶点覆盖问题要求图中顶点权重之和最小的顶点覆盖。这两个问题推广了经典的最大匹配与最小顶点覆盖问题,有重要的理论意义和广阔的应用前景。本文分析了这两个问题的计算复杂性,用整数规划理论证明了这两个问题的最优值在二部图结构下相等,并提供了多项式时间算法求解任意二部图上的这两个问题的最优解。我们的结果推广了Kǒnig定理,并为相关的装填与覆盖问题提供了有益的参考。(本文来源于《昆明理工大学》期刊2016-04-01）
郑光勇,徐雨明,李肯立,孙士兵[7]（2016）在《一种混合化学反应优化算法求解最小顶点覆盖问题》一文中研究指出最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。(本文来源于《计算机应用研究》期刊2016年09期）
陈吉珍,宁爱兵,支志兵,王永斐,张惠珍[8]（2015）在《最小顶点覆盖问题的加权分治算法》一文中研究指出最小顶点覆盖问题是组合优化中经典NP-Hard问题之一,其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术,该技术主要用于对分支降阶的递归算法进行复杂性分析,其核心思想可以理解为依据问题不同的特征设置一组相应的权值,以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题,并通过加权分治技术分析得出该算法的时间复杂度为O(1.255~n),优于常规分析下的时间复杂度O(1.325~n)。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。(本文来源于《运筹与管理》期刊2015年05期）
郭洪敏,殷志祥[9]（2015）在《基于DNA自组装模型解决图的最小顶点覆盖问题》一文中研究指出在分析最小顶点覆盖问题特点的基础上,以5个顶点的图为例,将最小顶点覆盖问题转化为可满足性问题,简化问题的操作难度。再根据DNA自组装的自发性和并行性等优势,通过建立DNA自组装模型解决可满足性问题,从而解决图的最小顶点覆盖问题。相对于传统算法,本算法只应用了凝胶电泳技术,大大的降低了操作难度和误差。(本文来源于《安徽理工大学学报(自然科学版)》期刊2015年03期）
王利民[10]（2015）在《最小权和的连通顶点P_3覆盖问题》一文中研究指出图的顶点覆盖问题是图论研究中的一个热点问题.给定一个简单图G=(E E),选取一个顶点子集S(?)V,如果图中的每一条边至少有一个顶点在集合S中,则称S是图G的一个顶点覆盖集.当图中的每一个顶点v∈V,赋予非负权值w(v),此时就是寻找一个顶点权和最小的顶点覆盖.这个问题是顶点删除问题的一个特殊类.顶点删除问题就是寻找一个最小权和的顶点子集使得从图上删除这些顶点后,剩下的顶点导出的子图满足一个给定的特征.例如：顶点反馈集问题就是寻找一个最小权和的顶点子集S(?)V(G)使得V-S导出的子图G[V一S]不包含圈.受到上述顶点删除问题的启发,作为推广介绍最小权和的连通顶点Pk覆盖问题：寻找一个最小权和的顶点子集S(?)V(G)使得V-S导出的子图G[V-S]不包含Pk路,且S导出的子图G[S]是连通的,其中Pk是指有k个顶点的路.在本论文中主要考虑k=3的情况.对于顶点P3覆盖问题,已经有许多比较好的结果Bostjan (2011)证明最小顶点Pk(k是整数,k≥2)覆盖问题在一般图上是NP-完全的,Tu和Zhou(2011)利用原始对偶近似算法给出最小权和的顶点P3覆盖问题的一个2因子近似解.考虑到连通性,Liu(2013)等人给出了最小的连通顶点Pk覆盖问题在单位圆盘图上的一个近似解.但对于顶点加权和连通性的情况还没有结果,为此本文在这两个条件下考虑顶点P3覆盖问题在一些特殊图上的近似算法.本文共有四章内容,主要是研究几类特殊图的最小权和的连通顶点P3覆盖问题的多项式时间近似格式.第一章给出了文章用到的相关符号,基本概念以及顶点Pk覆盖问题的应用背景和已有的结论,并进一步阐述本文的方法和主要结果.在第二章中,首先证明这个问题在网格图上的NP-复杂性,其次得出这个问题在单位圆盘图上的一个常因子近似解,最后在假设最小权和的连通顶点P3覆盖问题是c-局部的和图的最小度是2的条件下,本文证明在单位圆盘图上可以求得这个问题的一个多项式时间近似格式.在第叁章中,在最小权和的连通顶点P3覆盖问题是弱c-局部的和图的顶点权值是光滑性的条件下,本文证明在单位球图上可以求得这个问题的一个多项式时间近似格式.文章的最后,给出一些可以进一步探讨的问题.(本文来源于《南京师范大学》期刊2015-03-06）
最小顶点覆盖问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
针对DNA计算解决最小顶点覆盖覆盖问题,采用对空解的数据池进行解的删除操作,找出解的补集,重而获得问题的最优解。在链置换的基础上,代替酶的作用,提高了实验的效率,节省时间,此算法独特新颖,简单可靠。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最小顶点覆盖问题论文参考文献
[1].张文杰,涂建华.Series-Parallel图上最小权顶点覆盖3-路问题的有效算法[J].北京化工大学学报(自然科学版).2019
[2].张春露,殷志祥.图的最小顶点覆盖问题的链置换模型[J].佳木斯大学学报(自然科学版).2018
[3].巩成艳,殷志祥,赵鑫月.基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型[J].长春师范大学学报.2017
[4].占善华,谢小军.一种增量式约简方法求解最小顶点覆盖问题[J].计算机应用研究.2018
[5].郭洪敏.最小顶点覆盖问题的几种DNA算法研究[D].安徽理工大学.2016
[6].段侠.点赋权二部图上最大边装填问题和最小顶点覆盖问题的相关性及其算法研究[D].昆明理工大学.2016
[7].郑光勇,徐雨明,李肯立,孙士兵.一种混合化学反应优化算法求解最小顶点覆盖问题[J].计算机应用研究.2016
[8].陈吉珍,宁爱兵,支志兵,王永斐,张惠珍.最小顶点覆盖问题的加权分治算法[J].运筹与管理.2015
[9].郭洪敏,殷志祥.基于DNA自组装模型解决图的最小顶点覆盖问题[J].安徽理工大学学报(自然科学版).2015
[10].王利民.最小权和的连通顶点P_3覆盖问题[D].南京师范大学.2015
标签：Series-Parallel图; 顶点覆盖k-路问题; 有效算法; 动态规划;