Solving the Critical Node Problem using Metaheuristics

Affiliation: 
University of Turin
Co-authors: 
A. Grosso; P. Hosteins; R. Scatamacchia
Abstract: 
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.