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

图的控制集问题的近似算法研究

作　者: 丁玲玲
导　师: 方奇志
学　校: 中国海洋大学
专　业: 运筹学与控制论
关键词: 图的控制集部分控制集 NP-困难 Greedy算法原始-对偶算法
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 28次
引　用: 0次
阅　读: 论文下载

内容摘要

控制集问题是组合优化理论中一个有意义的,重要的研究领域。给定无向图G = (V,E)和顶点子集S (?) V ,如果对于?v∈V ,v∈S或v与S中的元素相邻,则称S是图G的一个控制集。一般的控制集问题是寻找图G的最小个数的控制集S。部分控制集问题是指对于给定的顶点赋权图G = (V,E;c)和正整数K,寻找图G的一个顶点子集T,使得在其控制下的顶点个数不小于K且使T中顶点权和达到最小。本文主要从算法和计算复杂性角度对控制集和部分控制集问题进行讨论。主要研究内容有:(1)将集合覆盖问题的近似算法理论应用到控制集问题中,给出了该问题的Greedy算法,原始-对偶算法和线性规划的舍入算法,进而对各算法的近似度进行了理论分析。(2)引入了部分控制集问题并建立了其整数规划模型。在证明了该问题的NP―困难性基础上,给出了修正Greedy算法和基于“参数修剪”技巧的原始-对偶算法,进而分析了算法的近似度。

全文目录

摘要  5-6
Abstract  6-8
第1章综述  8-16
  1.1 组合最优化问题与计算复杂性  8-11
    1.1.1 最优化问题  8-9
    1.1.2 NP-完备与NP-困难  9-11
  1.2 NP-困难问题的近似算法  11-12
  1.3 控制集问题的背景与模型  12-16
第2章控制集问题的近似算法  16-24
  2.1 控制集问题的定义及计算复杂性  16-17
  2.2 Greedy算法  17-19
  2.3 原始-对偶算法及其改进  19-22
  2.4 线性规划舍入算法  22-24
第3章部分控制集问题的近似算法  24-33
  3.1 部分控制集问题及其计算复杂性  24-25
  3.2 修正Greedy算法  25-28
  3.3 原始-对偶算法  28-33
参考文献  33-36
致谢  36-37
攻读硕士学位期间完成的文章  37

图的控制集问题的近似算法研究

内容摘要

全文目录

相似论文