【摘要】 本文提出了两个图支配集问题的变形即C强支配集和完全支配集问题,这两个问题都有重要的实际应用背景。我们证明了它们的判定问题是NP完全的,并且给出了它们相应优化问题的近似算法以及算法的近似度分析。更多还原

【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 corresponding optimization problems as well as their approximation ratios are also given.更多还原