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

Abstract:

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 maxim  mum vertex degree of the graph concerned）

Key words: dominating set, partial dominating set, primal-dual algorithm, approximation algorithm, performance ratio