论文部分内容阅读
参数化点覆盖问题(the Parameterized Vertex Cover Problem，简称PVC或VC)和最小点覆盖问题(the Minimum Vertex Cover Problem，简称Min-VC)是重要的NP难问题，研究人员对其算法包括参数化点覆盖问题的核心化算法做了大量的研究。本文首先对参数化点覆盖问题中目前主流的核心化算法进行综述。最近的结果表明NT算法本质上就是一种皇冠分解。本文通过对皇冠分解和NT算法这两种核心化方法的深入分析引出了两者之间存在的更强的内在联系。针对判断给定图是否存在皇冠的问题，本文提出了一般图中存在皇冠的充分必要判定定理。然后研究了皇冠分解和NT算法的等价性：利用严格皇冠和非严格皇冠的性质，证明了NT算法可以移除一般图中存在的所有严格皇冠。本文还提出了一种扩展NT算法，能够移除图中的所有严格和非严格皇冠，即证明了用扩展NT算法处理过的图中将不会存在任何皇冠结构。利用这个算法还可以判断给定图是否存在皇冠，这是一个多项式时间内的判定方法。本文还研究了最小点覆盖问题中的一种特殊情况。我们猜想最小点覆盖规模等于|V|／2时，该问题可以在多项式时间内解决。基于此，提出了最小点覆盖规模稍大于|V|／2时的精确算法和随机算法，扩展了算法的应用范围。本文最后对点覆盖问题的核心化算法和最小点覆盖问题算法的研究工作进行了总结，并阐述了将来对该问题进一步研究的一些工作。