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

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