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

参数化反馈顶点集问题的研究

作　者: 江国红
导　师: 陈建二
学　校: 中南大学
专　业: 计算机应用技术
关键词: 反馈顶点集固定参数枚举固定参数可解无向图竞赛图
分类号: TP301
类　型: 硕士论文
年　份: 2009年
下　载: 30次
引　用: 1次
阅　读: 论文下载

内容摘要

反馈顶点集(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问题的研究工作进行了总结,并阐述了对该问题的进一步研究工作。

全文目录

摘要  4-5
ABSTRACT  5-9
第一章绪论  9-14
  1.1 课题研究背景  9-11
  1.2 课题研究意义  11-12
  1.3 课题研究内容  12-13
  1.4 论文组织  13-14
第二章 FVS问题的研究现状  14-26
  2.1 相关定义  14-15
  2.2 无向图中FVS问题  15-19
    2.2.1 无向图中MFVS和MWFVS问题  15-16
    2.2.2 无向图中PFVS问题  16-19
  2.3 有向图中FVS问题  19-21
    2.3.1 一般有向图中FVS问题  19-20
    2.3.2 竞赛图上的FVS问题  20-21
  2.4 其他特殊图上的FVS问题  21-24
  2.5 小结  24-26
第三章 FVS问题的固定参数枚举  26-42
  3.1 相关定义和引理  26-28
  3.2 FVS的固定参数枚举算法  28-41
    3.2.1 元组构造  28-33
    3.2.2 基于元组的局部枚举  33-38
    3.2.3 固定参数枚举算法及分析  38-41
  3.3 小结  41-42
第四章竞赛图中参数化带权FVS问题  42-52
  4.1 相关定义及引理  42-43
  4.2 竞赛图中PW-MFVS的FPT算法  43-51
    4.2.1 求解Reduce-WFVST问题的算法  43-45
    4.2.2 基于分支搜索的算法  45-48
    4.2.3 基于动态规划的算法  48-51
  4.3 小结  51-52
第五章结束语  52-55
  5.1 研究工作总结  52-53
  5.2 进一步研究工作展望  53-55
参考文献  55-63
致谢  63-64
研究成果  64

参数化反馈顶点集问题的研究

内容摘要

全文目录

相似论文