关键词: 支配集问题 C强支配集 完全支配集 NPC,NP-hard 近似算法

Abstract: Two variations of the dominating set problem are presented, both of which have corresponding application background. In this paper, we prove the decision problems of the two variations are NPC. Furthermore, the approximation algorithms for their col-respo

Key words: Dominating set problem, Cstrong dominating set problem, Compl.ete dominating set problem, NPC, NP- hard, Approximation algorithm