论文部分内容阅读
皇冠分解和NT算法长久以来被认V1为是在参数化点覆盖的求核问题中有着广泛应用的两种相互独立的方法。NT算法将给定的图分成V2，V1和V1／2三部分，将砜和V1移除从而完成图的分解。而皇冠分解则是找到尽可能多的皇冠结构，删除这些皇冠以降低图规模。最近的研究结果表明NT算法和皇冠分解存在很强的内在联系：NT算法中的砜，V1部分正好构成一个皇冠结构。本文进一步研究了皇冠分解和NT算法的内在联系，提出了严格皇冠和非严格皇冠的概念，提出了一般图中存在皇冠的判定定理，证明了NT算法可以移除一般图中存在的所有严格皇冠。