Solving the Critical Node Problem using Metaheuristics

University of Turin
A. Grosso; P. Hosteins; R. Scatamacchia
We present two metaheuristics for the Critical Node Problem, i.e., the maximal fragmentation of a graph through the deletion of $k$ nodes, which exploits two smart and computationally efficient neighbourhoods. Solutions to improve the overall running time without deteriorating the quality of the solution computed are also illustrated.