论文摘要
控制集问题是组合优化理论中一个有意义的,重要的研究领域。给定无向图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算法和基于“参数修剪”技巧的原始-对偶算法,进而分析了算法的近似度。
论文目录
相关论文文献
- [1].超图的连通边控制集问题一个贪婪算法[J]. 现代商贸工业 2012(18)
- [2].构建最小k重控制集的概率算法[J]. 中国科学:数学 2011(08)
- [3].无线移动网络中k连通m控制集的一个维护算法[J]. 计算机技术与发展 2010(08)
- [4].关于图的控制集划分[J]. 江西师范大学学报(自然科学版) 2013(05)
- [5].基于混合逻辑动态模型的三相逆变电路有限控制集模型预测控制策略[J]. 电网技术 2014(02)
- [6].最小控制集问题的群集策略智能算法研究[J]. 科学技术与工程 2014(16)
- [7].传感器网络中最小k-连通m-控制集问题的近似算法[J]. 工程数学学报 2012(05)
- [8].关于倍图控制数的研究[J]. 哈尔滨师范大学自然科学学报 2014(06)
- [9].关于Bubblesort-star网络的距离控制数[J]. 计算机科学 2012(S3)
- [10].随机正则图中的一类新控制集[J]. 上海交通大学学报 2010(06)
- [11].De Bruijn和Kautz网络的k元控制[J]. 嘉兴学院学报 2012(06)
- [12].PWM-CSR有限控制集模型预测控制[J]. 电气传动 2014(10)
- [13].分布式供能系统在某学校实验大楼的控制集成[J]. 上海节能 2011(12)
- [14].无线ad hoc网络中定向连通控制集的局部构造算法[J]. 计算机工程与应用 2012(05)
- [15].260mm×300mm合金钢连铸坯质量控制集成技术的开发和应用[J]. 特殊钢 2011(02)
- [16].基于禁忌搜索的模拟退火算法在最小控制集中的应用[J]. 成都大学学报(自然科学版) 2013(02)
- [17].一种多步预测的变流器有限控制集模型预测控制算法[J]. 中国电机工程学报 2012(33)
- [18].图的关于边删除的外连通控制[J]. 河北师范大学学报(自然科学版) 2012(04)
- [19].氢生产的控制集成[J]. 软件 2010(06)
- [20].科研所三项科技成果 通过郑州局集团公司技术评审[J]. 郑铁科技 2018(04)
- [21].无线Ad hoc网络中干扰感知的拓扑管理[J]. 计算机技术与发展 2012(01)
- [22].加氢反应器除垢方法研究[J]. 当代化工 2011(06)
- [23].液晶彩电常用振荡控制IC OZ9925介绍(上)[J]. 家电检修技术 2014(02)
- [24].强乘积图与字典乘积图的控制数[J]. 五邑大学学报(自然科学版) 2010(03)
- [25].基于DSP+FPGA的混合电机控制器的设计[J]. 科技致富向导 2015(15)
- [26].无向de Bruijn图和Kautz图的k元控制[J]. 太原师范学院学报(自然科学版) 2010(03)
- [27].构建一类新网络簇的可靠性控制集[J]. 计算机学报 2013(06)
- [28].共轨系统与电子调速冷EGR系统的集成[J]. 硅谷 2011(10)
- [29].几类图的边控制划分[J]. 宜春学院学报 2013(09)
- [30].基于节点邻居关系的MCDS构造算法[J]. 计算机工程 2010(13)