| 图的部分控制集问题的修正 Greedy算法 |
| |
| 引用本文： | 丁玲玲,方奇志.图的部分控制集问题的修正 Greedy算法[J].运筹与管理,2007,16(5):83-86. |
| |
| 作者姓名： | 丁玲玲 方奇志 |
| |
| 作者单位： | 中国海洋大学,数学系,山东,青岛,266071 |
| |
| 基金项目： | 国家自然科学基金;教育部跨世纪优秀人才培养计划 |
| |
| 摘 要： | 部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。
|
| 关 键 词： | 运筹学 图的控制集 近似算法 NP-困难 |
| 文章编号： | 1007-3221（2007）05-0083-04 |
| 修稿时间： | 2007-05-31 |
Revised Greedy Algorithm for Partial Domination Problem |
| |
| DING Ling-ling,FANG Qi-zhi.Revised Greedy Algorithm for Partial Domination Problem[J].Operations Research and Management Science,2007,16(5):83-86. |
| |
| Authors: | DING Ling-ling FANG Qi-zhi |
| |
| Institution: | Department of Mathematics, Ocean University of China, Qingdao 266071, China |
| |
| Abstract: | |
| |
| Keywords: | operations research dominating set in graphs approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
