学位论文 > 优秀研究生学位论文题录展示

覆盖问题的参数算法研究

作　者: 李文军
导　师: 王建新
学　校: 中南大学
专　业: 计算机科学与技术
关键词: 超平面覆盖问题完美匹配顶点覆盖 NP完全性理论固定参数算法
分类号: O224
类　型: 硕士论文
年　份: 2010年
下　载: 63次
引　用: 0次
阅　读: 论文下载

内容摘要

覆盖问题是计算几何和组合优化领域中的一类重要的难解问题,对此类问题的研究不但具有重大的理论意义,而且在生物计算、电路设计、网络选址、工艺流程分析等应用领域具有许多重要的实际意义。人们从实际应用中抽象出了许多的覆盖问题,如顶点覆盖问题、树覆盖问题、超平面覆盖问题、集合覆盖问题等。本文主要对超平面覆盖问题和基于保证值的完美匹配图中顶点覆盖问题进行了深入的研究。对于超平面覆盖问题,本文首先通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,提出了一个时间复杂度为O*((0.736k)k)勺的确定性的参数算法,较大地改进了以前最好的时间复杂度为O*((k/2.2)2k)勺的算法。更一般地,我们还提出了关于超平面覆盖问题的确定性的参数算法,其时间复杂度为O*((dk)!/((d!)kk!)),较之前的时间复杂度为O*(kd(k+1))的算法亦有较大改进。对于完美匹配图中基于保证值的顶点覆盖问题,已有相关文献提出了一个时间复杂度为O*(15k)勺的固定参数算法。本文对此算法作了进一步的改进,其整体思路是首先采用迭代压缩技术将原问题转化为求一个特殊的具有完美匹配的Konig图上的最小顶点覆盖问题,然后将后者进一步转化为参数化2-ASLASAT问题的一个变种问题(KPM-2-AASAT问题),最后,通过深入分析问题的结构特征,我们采用分枝搜索技术和隐含参数技术求解KPM-2-AASAT问题。整个算法的时间复杂度为O*(9勺,较之前最好结果有较大改进。本文最后对上述两个问题的研究工作进行了总结,并对今后的相关研究工作做了简要的阐述。

全文目录

摘要  4-5
ABSTRACT  5-9
第一章绪论  9-17
  1.1 研究背景  9-11
  1.2 研究现状  11-14
    1.2.1 参数计算与复杂性理论的基本概念  11-12
    1.2.2 参数算法设计技术介绍  12
    1.2.3 参数算法分类及其应用示例  12-14
  1.3 研究内容  14-15
    1.3.1 参数化超平面覆盖问题FPT算法的研究  14-15
    1.3.2 完美匹配图中基于保证值的顶点覆盖问题FPT算法的研究  15
  1.4 研究意义  15-16
  1.5 论文组织  16-17
第二章超平面覆盖问题的固定参数算法  17-29
  2.1 引言  17-18
  2.2 直线覆盖问题  18-25
    2.2.1 相关性质和推论  18-19
    2.2.2 直线覆盖问题的算法  19-23
    2.2.3 算法LCA正确性证明和时间复杂度分析  23-25
  2.3 超平面覆盖问题  25-28
  2.4 小结  28-29
第三章完美匹配图中基于保证值的顶点覆盖问题的固定参数算法  29-46
  3.1 引言  29-31
  3.2 相关术语和问题的定义  31-35
    3.2.1 有关图的一些术语的定义  31-32
    3.2.2 有关可满足性问题(SAT)的一些术语的定义  32-34
    3.2.3 相关问题的定义  34-35
  3.3 P-PMK-VC问题的转化  35-39
    3.3.1 转化过程Transferl  35-37
    3.3.2 转化过程Transfer2  37-39
  3.4 PMK-2-AASAT问题的求解  39-43
    3.4.1 与P-2-AASAT问题有关的引理和定义  39-40
    3.4.2 PMK-2-AASAT问题的求解算法  40-43
  3.5 PM-AGV-VC问题的求解  43-45
  3.6 小结  45-46
第四章结束语  46-49
  4.1 研究工作总结  46-47
  4.2 进一步研究工作展望  47-49
参考文献  49-56
致谢  56-57
攻读硕士学位期间主要的研究成果  57

覆盖问题的参数算法研究

内容摘要

全文目录

相似论文