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

Revised Greedy Algorithm for Partial Domination Problem

作　　者：丁玲玲[1] 方奇志[1] 

机构地区：[1]中国海洋大学数学系,山东青岛266071

出　　处：《运筹与管理》2007年第5期83-86,共4页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(10771200);新世纪人才支持计划项目(NCET-05-0598)

摘　　要：部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。In this paper a kind of partial dominating set problems is discussed- given a vertex weighted graph G=（V,E;c） and a positive number K, the objective is to find a subset T∩V such that at least K vertices of V are dominated by T and the total vertex weight of T is minimized. First, the partial dominating set problem is shown to be NP-hard. Then a revised Greedy algorithm is proposed, which is proved to have the performance ratio H（K）.

关 键 词：运筹学 图的控制集 近似算法 NP-困难 

分 类 号：O224[理学—运筹学与控制论] O157.6[理学—数学]