We present two metaheuristics for the Critical Node Problem, that is, the maximal fragmentation of a graph through the deletion of k nodes. The two metaheuristics are based on the Iterated Local Search and Variable Neighborhood Search frameworks. Their main characteristic is to exploit two smart and computationally efficient neighborhoods which we show can be implemented far more efficiently than the classical neighborhood based on the exchange of any two nodes in the graph, and which we prove is equivalent to the classical neighborhood in the sense that it yields the same set of neighbors. Solutions to improve the overall running time without deteriorating the quality of the solution computed are also illustrated. The results of the proposed metaheuristics outperform those currently available in literature
Local search metaheuristics for the critical node problem / Aringhieri, Roberto; Grosso, Andrea; Hosteins, Pierre; Scatamacchia, Rosario. - In: NETWORKS. - ISSN 0028-3045. - 67:3(2016), pp. 209-221. [10.1002/net.21671]
Local search metaheuristics for the critical node problem
SCATAMACCHIA, ROSARIO
2016
Abstract
We present two metaheuristics for the Critical Node Problem, that is, the maximal fragmentation of a graph through the deletion of k nodes. The two metaheuristics are based on the Iterated Local Search and Variable Neighborhood Search frameworks. Their main characteristic is to exploit two smart and computationally efficient neighborhoods which we show can be implemented far more efficiently than the classical neighborhood based on the exchange of any two nodes in the graph, and which we prove is equivalent to the classical neighborhood in the sense that it yields the same set of neighbors. Solutions to improve the overall running time without deteriorating the quality of the solution computed are also illustrated. The results of the proposed metaheuristics outperform those currently available in literaturePubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2639531
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo