基于子图的随机图点覆盖2度点核化研究

点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形子图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论: 2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对顶点度概率分布为φ(x)的随机图的参数化点覆盖问题(G,k),当k小于某一与φ(x)有关的值时,它是2-核化可决策的.仿真结果证实,该理论能够把握2度点核化的内在机制,提供随机图上这一NP完全问题的求解方法,也为参数计算在已知度分布的一类不确定问题中的应用提供了可能.     

最小顶点覆盖快速降阶算法

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.     

一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法

二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为：当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖（ku,kl）时,对任意给定的近似率δ=1＋ε〉1,一定可以找到一个受约束近似点覆盖（ku,kl）,对应的近似率为max{ku^＊/ku,kl^＊/kl}≤1＋ε,整个近似算法的运行时间复杂度为O（22/ε）。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案（polynomial time approximation scheme,PTAS算法）。     

顶点覆盖问题线性内核算法

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1．1033^n),参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。     

最多叶子生成树问题的核化算法

对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.     

基于可满足解空间的DNA算法--解决最小顶点覆盖问题

论文给出了基于可满足解空间的最小顶点覆盖问题的DNA算法,该算法直接生成可满足解空间,无须在全体解空间中进行各种过滤过程。在对图中的顶点进行适当的编码后,使用常规的生物操作完成可满足解空间的产生及最终解的分离。最后指出了该算法的优点、存在问题及下一步的研究方向。     

一种求解平面图的最小顶点覆盖算法

最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独立集算法,从而求出最小顶点覆盖。通过实验结果的比对验证算法的正确性和有效性。     

一种求解顶点覆盖问题的混合遗传算法

顶点覆盖问题是一个NP难问题,在排序、计算机网络等现实生活中有许多的应用。使用基本遗传算法进行搜索时,存在着局部搜索能力较弱的不足,本文提出了一种新的求解最小顶点覆盖问题的混合遗传算法,将基本遗传算法与局部优化策略相结合,改善遗传算法的局部搜索能力,加快求解该问题的速度。对几种典型无向图的实验证实了新方法的有效性,其整体性能优于现有的一些顶点覆盖问题遗传算法。     

基于核心化技术的点覆盖改进算法

点覆盖是一个著名的NP难解问题,在通信网络和生物信息学等领域具有重要应用。针对点覆盖的研究主要集中在启发式或近似算法,其主要不足是无法实现全局最优。核心化是处理难解问题的一种新方法。提出融合启发式操作和核心化操作的算法框架,利用核心化技术进行点覆盖启发式算法优化。核心化操作挖掘出全局最优的顶点集,而启发式操作改变网络拓扑,使下一轮核心化操作能够继续,两者交叉执行实现解精度优化。实验结果表明,提出的算法在不同网络中均能实现不同程度的优化,在几乎所有稀疏网络实例中获得了最优解。