论文部分内容阅读
本文针对三个NP-hard图修改问题设计固定参数可解算法。第一个问题是如何从一个简单的无向图中删除最少的结点,使得剩余的图中所有顶点的度都不大于3。在前人所给的时间复杂度为0*(3.24k)的固定参数算法中,先删除度大于3的结点,然后处理两个直接相连的度都为3的结点,考虑到这两个结点的邻居,这种情况会分出很多种子情况,其中它们的四个邻居都为1的那种情况最为复杂,最后处理度为3的结点。本文针对该算法中最复杂的情况,通过考虑这两个结点的邻居的邻居来进行细分,且对细分出的每一种情况进行单独处理：根据分析删除最少的结点使得该情况满足条件,最终把时间复杂度降到了O*(3.1k)。第二个问题是如何从给定的有向图中删除最少的结点,使得剩余的图中的每个结点的出度和入度都小于2。本文采用深度受限搜索树技术设计了固定参数可解算法。该算法首先删除出度和入度都大于3的结点,然后分析余下的图,通过出度和入度的值来分情况处理,由于出度入度的值最大就为3,所以总共有七种情况。并且对每种情况都给出相应的处理：删除掉最少的结点使得该情况出度和入度都符合小于等于1的要求。该算法的时间复杂度为O*(3k)。第三个问题是如何从给定的无向图中删除最少边后,剩余的图中的每条边的两个端点的度至少有一个小于2。本文用深度受限搜索树技术设计了固定参数可解算法。先对无向图进行预处理,首先把度大于2的结点全部标记为黑点,然后再把两端都是黑点的边标记为黑边,接着处理标记后图中的黑边：第一步处理三条直接相连且无公共端点的黑边,即删除掉中间的黑边；第二步处理两条直接相连的黑边,即随机选择一条黑边删除；第三直接删除图中剩下的所有黑边。该算法的时间复杂度为O*(2k)。