控制集与部分控制集问题的原始-对偶算法  

The Primal-Dual Algorithms for the Dominating Set and Partial Dominating Set Problems

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

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

出　　处：《计算机工程与科学》2008年第12期102-104,共3页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(10771200)

摘　　要：图的控制集问题是一类应用广泛的组合最优化问题。本文利用控制集和部分控制集问题的整数规划模型和原始-对偶方法,分别给出这两个问题近似度为Δ+1的近似算法(Δ为图中顶点最大度)。The dominating set and partial dominating set problems are important combinatorial optimization problems in many applications. Based on their integer program models and the primal-dual method, two approximation algorithms are proposed, both of which have the performance ratio △＋ 1 （ △ is the maximum vertex degree of the graph concerned）.

关 键 词：控制集 部分控制集 原始-对偶算法 近似算法 近似度 

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