导读:本文包含了反馈顶点集论文开题报告文献综述及选题提纲参考文献，主要关键词:NP难问题,精确算法,测量治之,子集反馈顶点集问题
反馈顶点集论文文献综述
周晓清,肖鸣宇[1]（2018）在《无向图中子集反馈顶点集问题的精确算法》一文中研究指出子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O~*(2~n)的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O~*(1.8638n)的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O~*(1.7743n).文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.(本文来源于《计算机学报》期刊2018年03期）
王建新,江国红,陈建二[2]（2010）在《带权无向图中反馈顶点集的固定参数枚举算法》一文中研究指出反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).(本文来源于《计算机学报》期刊2010年07期）
江国红[3]（2009）在《参数化反馈顶点集问题的研究》一文中研究指出反馈顶点集(Feedback Vertex Set,简称FVS)问题是经典的NP难问题,在电路测试、操作系统解死锁、网络设计、分析工艺流程、生物计算等领域都有重要应用。人们提出了一系列解决FVS问题算法技术,包括近似算法、精确算法和随机算法等。随着参数计算理论的发展,近年来参数化FVS问题引起了人们的重视,并对此问题的研究取得了很大突破。目前已经证明了无向图和有向图中FVS问题都是固定参数可解的(fixed-parameterized tractable,简称FPT)。本文研究了带权无向图中FVS问题的固定参数枚举技术,提出了一种有效的基于分支搜索技术的固定参数枚举算法。首先求出给定图G的一个含k个顶点的FVS F;然后基于F对图G进行结构划分,对各结构划分利用分支搜索技术求得满足一定条件的图结构,从而将FVS问题转化为反馈边集(Feedback Edge Set,简称FES)问题;最后通过枚举z个权值最大森林来枚举z个权值最小的FES,进而枚举出z个权值最小的含k个顶点的FVS。整个算法时间复杂度为O(5~kkn~2+(5~k+3~kz)n~2 logn)。本文还研究了竞赛图(Tournaments)的参数化带权FVS问题,即在竞赛图中找一个权值最小的含顶点数不超过k的FVS。首先,利用求解竞赛图中不带权FVS问题的FPT算法求出一个含k个点的FVS F;然后对F进行划分,并对每种划分,将问题转化为相同子序列(Common Subsequence)问题而求得基于此划分的权值最小的FVS;基于所有划分的FVS中权值最小的一个FVS即为问题的解。本文分别用分支搜索和动态规划两种技术求解相同子序列问题,从而对参数化带权FVS问题提出了时间复杂度分别为O(3~kn)和O(2~kn~2(logn+k))的算法。本文最后对FVS问题的研究工作进行了总结,并阐述了对该问题的进一步研究工作。(本文来源于《中南大学》期刊2009-04-01）
反馈顶点集论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
反馈顶点集论文参考文献
[1].周晓清,肖鸣宇.无向图中子集反馈顶点集问题的精确算法[J].计算机学报.2018
[2].王建新,江国红,陈建二.带权无向图中反馈顶点集的固定参数枚举算法[J].计算机学报.2010
[3].江国红.参数化反馈顶点集问题的研究[D].中南大学.2009