We present two metaheuristics for the Critical Node Problem, that is, the maximal fragmentation of a graph through the deletion of inline image 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 Cesare;HOSTEINS, Pierre;
2016

Abstract

We present two metaheuristics for the Critical Node Problem, that is, the maximal fragmentation of a graph through the deletion of inline image 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.
67
3
209
221
http://onlinelibrary.wiley.com/doi/10.1002/net.21671/abstract
R. Aringhieri; A. Grosso; P. Hosteins; R. Scatamacchia
File in questo prodotto:
File Dimensione Formato  
2016-CNP-Networks-postPrint.pdf

Accesso aperto con embargo fino al 19/02/2017

Descrizione: Post Print
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 660.29 kB
Formato Adobe PDF
660.29 kB Adobe PDF Visualizza/Apri
2016-CNP-Networks-online.pdf

Accesso riservato

Descrizione: PDF editoriale
Tipo di file: PDF EDITORIALE
Dimensione 767.78 kB
Formato Adobe PDF
767.78 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2318/1509060
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 36
  • ???jsp.display-item.citation.isi??? 30
social impact