基于混合策略的动态图顶点覆盖边增量自适应算法

唐文睿; 陈京荣; 张雪倩

doi:10.16088/j.issn.1001-6600.2025121802

广西师范大学学报（自然科学版） ›› 2026, Vol. 44 ›› Issue (5) : 101 -111. DOI: 10.16088/j.issn.1001-6600.2025121802

基于混合策略的动态图顶点覆盖边增量自适应算法

唐文睿, 陈京荣, 张雪倩

作者信息 +

Author information +

文章历史 +

摘要

顶点覆盖问题是图论中一个经典的组合优化问题，在实际问题中具有重要应用。对于动态图环境，随着边不断增量式加入，传统静态算法需从头求解，计算代价高且难以保持解结构的稳定性，因此，本文提出混合策略边增量顶点覆盖算法(hybrid edge-incremental vertex cover, HEIVC)。算法在初始极小顶点覆盖基础上，融合快速候选生成、子图局部搜索与边独立子集划分与冲突图的候选构造3种互补策略，并通过自适应模块选择机制在不同增量尺度和局部扰动条件下动态调整启用策略，旨在保证解合法性与极小性的同时提高稳定性与质量。对比现有2-近似贪心算法和IMVC算法，结果表明，HEIVC在不同模块组合下的覆盖规模表现出显著优势，验证了算法在动态图增量维护中的有效性。