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