Hybridization of GRASP with Exterior Path Relinking for Identifying Critical Nodes in Graphs

摘要

This paper deals a problem with detecting the critical nodes in order to achieve minimum pair-wise connectivity in the residual graph after removing a limited number of nodes from the graph. It is called the critical node detection problem (CNDP). In this paper, we propose a new hybridization scheme of greedy randomized adaptive search procedure (GRASP) with exterior path-relinking. Exterior path-relinking, a recently proposed metaheuristic method, creates paths of successive solutions starting from two high-quality solutions to other high quality solutions. A randomly selected solution from the elite solution pool collecting throughout GRASP iterations and the resulting solution from each GRASP iteration are relinked by exterior path-relinking for finding better solutions. The proposed algorithm is assisted on test instances from the literature. Computational experiments demonstrate that the proposed method outperforms other existing algorithms in the area of CNDP.