Heuristic Algorithm for Identifying Critical Nodes in Graphs

Dalaijargal Purevsuren, Gang Cui, Nwe Nwe Htay Win, Xiufeng Wang


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.


Combinatorial Optimization; Heuristic Search; GRASP with Path Relinking; Critical Node Detection Problem

Full Text:



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.

Lululemon Black Friday cheap nfl jerseys Lululemon factory Outlet ny Black Friday discount tiffany outlet wholesale soccer jerseys online oakley black friday cheap nhl jerseys china cheap nfl jerseys north face black friday sale cheap nfl jerseys online Jordans Black Friday Sale 2015 Cheap Moncler Cyber Monday moncler outlet cheap soccer jerseys moncler outlet black friday cheap authentic nfl jerseys north face cyber monday Louboutin Black Friday canada wholesale cheap nfl jerseys lululemon cyber monday 2015 cheap nfl jerseys from china 2015 Cheap Moncler Black Friday Sale Moncler Cyber Monday 2015 cheap jerseys Lululemon Cyber Monday Sale jordans cyber monday deals 2015 cheap nike nfl jerseys Black Friday deals Lululemon 2015 jordan black friday 2015 Moncler Jackets Black Friday Sale 2015 Louboutin Pas Cher Black Friday 2015 Canada Lululemon north face black friday cheap wholesale soccer jerseys