图的部分控制集问题的修正 Greedy算法

图的部分控制集问题的修正 Greedy算法

部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小.本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明.

作 者： 丁玲玲 方奇志 DING Ling-ling FANG Qi-zhi   作者单位： 中国海洋大学,数学系,山东,青岛,266071  刊 名： 运筹与管理  ISTIC PKU 英文刊名： OPERATIONS RESEARCH AND MANAGEMENT SCIENCE  年，卷(期)： 2007 16(5)  分类号： O224 O157.6  关键词： 运筹学   图的控制集   近似算法   NP-困难  

【图的部分控制集问题的修正 Greedy算法】相关文章：

机场停机位分配问题的图着色模型及其算法04-26

基于修正因子智能权函数的汽车ABS模糊控制算法仿真研究04-27

多层次图排序算法及其在图剖分中的应用04-26

飞艇压力控制系统的算法设计与仿真04-27

微型涡喷发动机控制算法研究04-26

红外地球敏感器测量值修正算法及其应用研究04-27

高分辨率压力修正算法在全速流动中的研究与应用04-26

网络分层用于最短路问题的算法研究04-27

一类优化问题的快速收敛算法04-26

水环境逆边界逆动态混合控制精确算法04-27