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

摘要：

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

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

所属期刊栏目：34

分类号：TP3(计算技术、计算机技术)

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

在线出版日期：2007-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：177-178,186