Advances in Computer Science : an International Journal
Heuristic Algorithm for Identifying Critical Nodes in Graphs
Abstract
The paper presents Greedy Randomized Adaptive Search Procedure with Path Relinking (GRASP with PR) for the Critical Node Detection Problem (CNDP). An evolutionary Path Relinking mechanism is added to GRASP with PR to intensify. Our computational experiments show that this algorithm is a competitive method compared with the previously proposed methods for solving CNDP such as Variable Neighborhood Search and Simulated Annealing.
Keywords
Full Text:
PDFReferences
A. Arulselvan, C. W. Commander, L. Elefteriadou, and P. M. Pardalos, “Detecting critical nodes in sparse graphs”, Computers & Operations Research, Vol. 36, No. 7, 2009, pp. 2193–2200.
M. Di Summa, A. Grosso, and M. Locatelli, “Complexity of the critical node problem over trees”, Computers & Operations Research, Vol. 38, No. 12, 2011, pp. 1766–1774.
B. Addis, M. Di Summa, and A. Grosso, “Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth”, Discrete Applied Mathematics, Vol. 161, No. 16–17, 2013, pp. 2349–2360.
S. Shen and J. C. Smith, “Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs”, Networks, Vol. 60, No. 2, 2012, pp. 103–119.
M. Di Summa, A. Grosso, and M. Locatelli, “Branch and cut algorithms for detecting critical nodes in undirected graphs”, Computational Optimization and Applications, Vol. 53, No. 3, 2012, pp. 649–680.
M. Ventresca and D. Aleman, “A derandomized approximation algorithm for the critical node detection problem”, Computers & Operations Research, Vol. 43, 2014, pp. 261–270.
M. Ventresca, “Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem”, Computers & Operations Research, Vol. 39, No. 11, 2012, pp. 2763–2775.
R. Aringhieri, A. Grosso, P. Hosteins, and R. Scatamacchia, “VNS solutions for the Critical Node Problem”, Electronic Notes in Discrete Mathematics, Vol. 47, 2015, pp. 37–44.
M. G. C. RESENDE and C. C. Ribeiro, “GRASP: Greedy randomized adaptive search procedures”, in Search Methodologies - Introductory tutorials in optimization and decision support systems, 2nd ed., Springer, 2014, pp. 287–312.
P. Festa and M. G. C. RESENDE, “Hybridizations of GRASP with Path-Relinking”, in Hybrid Metaheuristics, Vol. 434, Berlin Heidelberg: Springer, 2013, pp. 135–155.
F. Glover, “Tabu Search and Adaptive Memory Programming — Advances, Applications and Challenges”, in Interfaces in Computer Science and Operations Research, Vol. 7, Springer US, 1997, pp. 1–75.
