10.3969/j.issn.1002-137X.2007.01.050
图的支配集若干问题的研究
本文提出了两个图支配集问题的变形即C强支配集和完全支配集问题,这两个问题都有重要的实际应用背景.我们证明了它们的判定问题是NP完全的,并且给出了它们相应优化问题的近似算法以及算法的近似度分析.
支配集问题、C强支配集、完全支配集、NPC、NP-hard、近似算法
34
TP3(计算技术、计算机技术)
国家自然科学基金60496321;60373021;上海市科技发展基金03JC14014
2007-03-26(万方平台首次上网日期,不代表论文的发表时间)
共3页
177-178,186