加权分治与皇冠技术求解最大加权独立集

皇冠分解技术是一种算法优化技术,通过找出一个称为皇冠的特殊非空独立集,并将该独立集和它的邻接集合删除,得到一个不含皇冠的子图,从而降低原问题规模,降低算法时间复杂度。针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集。首先构造了一个二分图,并通过该图找出皇冠结构,采用皇冠分解技术分解图,针对无皇冠的子图设计了一个分支降阶递归算法,然后利用加权分治技术对算法时间复杂度进行分析,最终得到一个优于常规时间复杂度的精确算法。

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

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

参数计算中核心化技术及其应用

在参数计算与复杂性理论中,一个参数问题是固定参数可解的问题当且仅当该问题是可核心化的.核心化技术是参数化算法设计中应用最为广泛、有效的技术,是参数理论中的一个研究热点.通过实例分析对比了最主要的4种核心化技术的基本思想、应用特点和方法,总结了核心化技术在cover类、packing类和cut类等几个重要领域中的应用成果,展望核心化技术的进一步研究方向并加以分析讨论,针对核心化新技术研究和某些热点问题,提出了可能采取的核心优化方法和思路.

Paw图–边删除问题的线性顶点核心化算法

图边删除问题中一类重要问题是研究是否可以删除图中不超过k条边之后使得剩余的图不存在某个子图结构H,而子图H为顶点个数不超过4的连通图的情况被研究得最为广泛.本文主要考虑H为Paw图(三角形其中一个顶点再邻接一条边)的情况,称为Paw图–边删除问题,并为该问题设计了一个32k个顶点的问题核.这是该问题的第1个线性顶点大小的问题核.文中主要的技术是结合两个新的皇冠分解的变体来分析图的结构从而对图进行简化.