摘要
本文提出了两个图支配集问题的变形即C强支配集和完全支配集问题,这两个问题都有重要的实际应用背景。我们证明了它们的判定问题是NP完全的,并且给出了它们相应优化问题的近似算法以及算法的近似度分析。
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-responding optimization problems as well as their approximation ratios are also given.
出处
《计算机科学》
CSCD
北大核心
2007年第1期177-178,186,共3页
Computer Science
基金
国家自然科学基金第60496321和60373021号
上海市科技发展基金第03JC14014号资助
关键词
支配集问题
C强支配集
完全支配集
NPC
NP-hard
近似算法
Dominating set problem, Cstrong dominating set problem, Compl.ete dominating set problem, NPC, NP- hard, Approximation algorithm
