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

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

An improved vertex cover algorithm based on kernelization

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.