一种移除所有皇冠的扩展NT算法

摘要：

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

关键词：点覆盖、参数计算、核心化算法、皇冠分解、NT算法

所属期刊栏目：34

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60433020

在线出版日期：2007-12-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：173-176,191