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

计算机工程与科学

• 计算机网络与信息安全 • 上一篇下一篇

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

骆伟忠，蔡昭权

(惠州学院信息科学技术学院,广东惠州 516007)

收稿日期:2016-12-12 修回日期:2017-06-28 出版日期:2018-08-25 发布日期:2018-08-25
基金资助:
国家自然科学基金(61370185)；广东省自然科学基金博士启动项目(2015A030310445)；惠州学院博士启动项目(C513.0211)

An improved vertex cover algorithm

based on kernelization

LUO Weizhong,CAI Zhaoquan

(School of Information Science and Technology,Huizhou University,Huizhou 516007,China)

Received:2016-12-12 Revised:2017-06-28 Online:2018-08-25 Published:2018-08-25

摘要/Abstract

摘要：

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

关键词: 点覆盖, NP难解, 核心化, 启发式算法, 参数计算

Abstract:

Vertex cover is a famous NPhard problem and has important applications in many fields such as communication networks, bioinformatics and so on. Current researches mainly study it from the aspects of heuristic algorithms or approximate algorithms, which cannot achieve global optimization. Kernelization is a new approach dealing with hard problems. We propose an algorithm framework combining heuristic operation and kernelization operation and apply the kernelization technique to optimizing heuristic vertex cover algorithms. Kernelization operation identifies the set of vertices belonging to some optimal solutions, while heuristic operation changes the network topology, which guarantees that the kernelization operation can be executed successfully in the next loop.The optimization is achieved by interleaving the kernelization operation and heuristic operation. Simulation results show that the proposed algorithm can achieve various degrees of optimization in different networks. Moreover, it can obtain the optimal solution in almost all sparse network instances.

Key words: vertex cover, NP-hard, kernelization, heuristic algorithm, parameterized computation

骆伟忠，蔡昭权. 基于核心化技术的点覆盖改进算法[J]. 计算机工程与科学.

LUO Weizhong,CAI Zhaoquan.

An improved vertex cover algorithm

based on kernelization

[J]. Computer Engineering & Science.

[1]	张贝, 闵华松, 张新明. 差分变异和领地搜索的平衡优化算法及其机器人路径规划[J]. 计算机工程与科学, 2023, 45(11): 2078-2090.
[2]	包敏泽, 胡秀婷, 谢玉莹, 蒋波. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(06): 1127-1133.
[3]	陈秀兰，刘婷. 基于动态奖惩的CDCL SAT求解器分支启发式算法[J]. 计算机工程与科学, 2019, 41(03): 490-497.
[4]	李永伟1,2，刘树安3，郭晋秦1. 普通立体仓库的货位优化模型与算法研究[J]. 计算机工程与科学, 2019, 41(02): 321-327.
[5]	黄洪涛1，武继刚1，郑露露1，缪裕青2. 面向无线内容分发网络的树形拓扑生成算法[J]. 计算机工程与科学, 2018, 40(12): 2133-2140.
[6]	罗裕春,武继刚,史雯隽,贺子楠. 移动云计算中的任务调度与计算迁移算法[J]. 计算机工程与科学, 2018, 40(11): 1915-1924.
[7]	张耀国1，武继刚2，高任飞1. 具有可控冗余度的虚拟机容错分配算法[J]. 计算机工程与科学, 2017, 39(09): 1617-1626.
[8]	熊李军1，谢政2，陈挚2，张军3. 基于多约束QoS问题的启发式算法[J]. J4, 2011, 33(9): 19-23.
[9]	赵娟, 潘耘. Overlay多播网络中带度约束的最小带宽多播树的求解[J]. J4, 2010, 32(3): 28-30.
[10]	叶吉祥, 徐玉良. 基于混沌PSO算法的求解电力公司最优报价策略研究[J]. J4, 2010, 32(2): 150-153.
[11]	洪翔宇蔡晟. 顶点覆盖变体问题的确定参数可解算法研究[J]. J4, 2008, 30(12): 79-81.
[12]	胡华平吕曾望刘波王璞. 非授权局域网拓扑探测系统的设计与实现[J]. J4, 2006, 28(11): 12-14.
[13]	尹国定[1] 于战科[2] 倪明放[2]. 多约束QoS路由的一种启发式算法[J]. J4, 2004, 26(2): 53-55.
[14]	李克文吴孟达张雄明. 约简的一种启发式算法[J]. J4, 2004, 26(1): 92-94.

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

An improved vertex cover algorithm

based on kernelization

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 14

编辑推荐

Metrics

本文评价