论文部分内容阅读
图上的控制集问题已经得到广泛的研究，本文提出了一种新型的控制集问题，即限制性控制集问题．给定赋权图G=(V,E;c，w)及正整数K，c，w：V→R+．寻找G的控制集D，满足D中每个点所控制的点的w权重之和不超过K，使得c(D)达到最小．对此问题，文中给出两种不同的模型，D中的元素不能重复选取和D中的元素可以重复选取．我们得到如下结果：(1)在第一种模型下，问题是强NP-难的，不存在近似值为3/2-ε的多项式算法，这里ε>0；当所给图是一棵树时，此问题是NP-完备的，我们设计出启发式算法，当c(v)=w(v)=1，Av∈V时，我们设计出多项式算法．(2)在第二种模型下，即使所给图是一棵树，此问题仍是强NP-难的，不存在近似值为3/2-ε的多项式算法，我们也设计出启发式算法，当c(v)=w(v)=1，Av∈V时，我们也设计出多项式算法。
论文主要有以下章节构成：
第一章：回顾了问题的由来，介绍了到目前为止的一些研究成果及本文的一些结果。
第二章：介绍本论文涉及到的有关图论、组合最优化、近似算法方面的基本概念、符号和术语。
第三章：分别讨论了图上的限制性控制集问题的两种模型的NP-完备性并对特殊子问题给出算法。
第四章：结论和未来的研究方向．