导读:本文包含了固定参数可解论文开题报告文献综述及选题提纲参考文献，主要关键词:顶点删除,搜索树,固定参数可解
固定参数可解论文文献综述
李彬[1]（2013）在《叁个图修改问题的固定参数可解算法研究》一文中研究指出本文针对叁个NP-hard图修改问题设计固定参数可解算法。第一个问题是如何从一个简单的无向图中删除最少的结点,使得剩余的图中所有顶点的度都不大于3。在前人所给的时间复杂度为0*(3.24k)的固定参数算法中,先删除度大于3的结点,然后处理两个直接相连的度都为3的结点,考虑到这两个结点的邻居,这种情况会分出很多种子情况,其中它们的四个邻居都为1的那种情况最为复杂,最后处理度为3的结点。本文针对该算法中最复杂的情况,通过考虑这两个结点的邻居的邻居来进行细分,且对细分出的每一种情况进行单独处理：根据分析删除最少的结点使得该情况满足条件,最终把时间复杂度降到了O*(3.1k)。第二个问题是如何从给定的有向图中删除最少的结点,使得剩余的图中的每个结点的出度和入度都小于2。本文采用深度受限搜索树技术设计了固定参数可解算法。该算法首先删除出度和入度都大于3的结点,然后分析余下的图,通过出度和入度的值来分情况处理,由于出度入度的值最大就为3,所以总共有七种情况。并且对每种情况都给出相应的处理：删除掉最少的结点使得该情况出度和入度都符合小于等于1的要求。该算法的时间复杂度为O*(3k)。第叁个问题是如何从给定的无向图中删除最少边后,剩余的图中的每条边的两个端点的度至少有一个小于2。本文用深度受限搜索树技术设计了固定参数可解算法。先对无向图进行预处理,首先把度大于2的结点全部标记为黑点,然后再把两端都是黑点的边标记为黑边,接着处理标记后图中的黑边：第一步处理叁条直接相连且无公共端点的黑边,即删除掉中间的黑边；第二步处理两条直接相连的黑边,即随机选择一条黑边删除；第叁直接删除图中剩下的所有黑边。该算法的时间复杂度为O*(2k)。(本文来源于《山东大学》期刊2013-04-05）
刘运龙,王建新[2]（2010）在《带权最大割问题的一种基于划分技术的固定参数可解算法》一文中研究指出运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题及其相关概念进行了参数化定义,然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行[1n(1/ε)]×2~k(0<ε<1)次随机划分,并选择其中权值最大的k-划分作为输出解,因而能在时间O~*(1n(1/ε)2~k)内以至少1-ε的概率找到目标解。接着在此基础上着重运用最新改进的(n,k)-全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O~*(2~(2k+12log~2(2k))的确定性算法,表明了带权最大割问题是固定参数可解的。(本文来源于《高技术通讯》期刊2010年03期）
刘运龙,陈建二,王建新[3]（2008）在《带权Matching和Packing问题的一种固定参数可解算法》一文中研究指出带权的m-DMATCHING和m-SETPACKING问题(m≥3)以前是用近似算法来求解的.本文首先根据参数计算理论对这两个带权问题进行了参数化定义,然后运用最新的着色技术和动态规划技术对带权的m-SETPACKING问题设计了一个时间复杂度为O*(12.8mk)的固定参数可解算法,接着在此基础上利用问题本身的结构特点对带权的m-DMATCHING问题提出了一个时间复杂度为O*(12.8(m-1)k)的固定参数可解算法,表明带权的m-SETPACKING问题和带权的m-DMATCHING问题都是固定参数可解的.(本文来源于《小型微型计算机系统》期刊2008年04期）
固定参数可解论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题及其相关概念进行了参数化定义,然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行[1n(1/ε)]×2~k(0<ε<1)次随机划分,并选择其中权值最大的k-划分作为输出解,因而能在时间O~*(1n(1/ε)2~k)内以至少1-ε的概率找到目标解。接着在此基础上着重运用最新改进的(n,k)-全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O~*(2~(2k+12log~2(2k))的确定性算法,表明了带权最大割问题是固定参数可解的。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
固定参数可解论文参考文献
[1].李彬.叁个图修改问题的固定参数可解算法研究[D].山东大学.2013
[2].刘运龙,王建新.带权最大割问题的一种基于划分技术的固定参数可解算法[J].高技术通讯.2010
[3].刘运龙,陈建二,王建新.带权Matching和Packing问题的一种固定参数可解算法[J].小型微型计算机系统.2008