图的支配集若干问题的研究  

Some Variations of Dominating Set Problem

作　　者：李镇坚[1] 葛启[1] 王海涛[1] 朱洪[1] 

机构地区：[1]复旦大学计算机科学与工程系,上海200433

出　　处：《计算机科学》2007年第1期177-178,186,共3页Computer Science

基　　金：国家自然科学基金第60496321和60373021号;上海市科技发展基金第03JC14014号资助

摘　　要：本文提出了两个图支配集问题的变形即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.

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

分 类 号：O157.5[理学—数学]