三个图修改问题的固定参数可解算法研究

摘要

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

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 国内外研究现状

1．3 本文的主要工作

1．4 本文的组织结构

第二章 Co-Path／Cycle Packing问题的算法研究

2．1 问题介绍及预备知识

2．1．1 相关定义介绍

2．1．2 性质介绍

2．2 算法描述

2．2．1 前人算法描述

2．2．2 对算法的改进

第三章 有向图的Co-Path／Cycle packing问题

3．1 概念描述

3．2 问题描述及算法思路描述

3．3 处理方法

3．4 问题总结与方法分析

第四章 度受限的边删除问题

4．1 预备知识及问题描述

4．2 相关性质约减规则及内核分析

4．3 处理方法

4．4 问题总结与方法分析

第五章 总结与展望

参考文献

致谢