@article{Chen2024, 
author = {Zhi-Han Chen and Shao-Wei Cai and Jian Gao and Shi-Ke Ge and Chan-Juan Liu and Jin-Kun Lin},
title = {Heuristic Search with Cut Point Based Strategy for Critical Node Problem},
year = {2024},
journal = {Journal of Computer Science and Technology},
volume = {39},
number = {6},
pages = {1328-1340},
keywords = {local search, cut point, heuristic search, critical node problem},
url = {https://www.sciopen.com/article/10.1007/s11390-024-2850-0},
doi = {10.1007/s11390-024-2850-0},
abstract = {The critical node problem (CNP) aims to deal with critical node identification in a graph, which has extensive applications in many fields. Solving CNP is a challenging task due to its computational complexity, and it attracts much attention from both academia and industry. In this paper, we propose a population-based heuristic search algorithm called CPHS (Cut Point Based Heuristic Search) to solve CNP, which integrates two main ideas. The first one is a cut point based greedy strategy in the local search, and the second one involves the functions used to update the solution pool of the algorithm. Besides, a mutation strategy is applied to solutions with probability based on the overall average similarity to maintain the diversity of the solution pool. Experiments are performed on a synthetic benchmark, a real-world benchmark, and a large-scale network benchmark to evaluate our algorithm. Compared with state-of-the-art algorithms, our algorithm has better performance in terms of both solution quality and run time on all the three benchmarks.}
}