We present a VNS algorithm for the Critical Node Problem, i.e., the maximal fragmentation of a graph through the deletion of k nodes. Two computational efficient neighbourhoods are proposed proving also their equivalence to the straightforward exchange of two nodes. The results of the proposed VNS algorithms outperform those currently available in literature.

VNS solutions for the critical node problem

ARINGHIERI, ROBERTO;GROSSO, Andrea Cesare;HOSTEINS, Pierre;
2015

Abstract

We present a VNS algorithm for the Critical Node Problem, i.e., the maximal fragmentation of a graph through the deletion of k nodes. Two computational efficient neighbourhoods are proposed proving also their equivalence to the straightforward exchange of two nodes. The results of the proposed VNS algorithms outperform those currently available in literature.
International Conference on Variable Neighborhood Search
Djerba
2014
47
37
44
R. Aringhieri; A. Grosso; P. Hosteins; R. Scatamacchia
File in questo prodotto:
File Dimensione Formato  
2015-ENDM-VNS-CNP.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 204.9 kB
Formato Adobe PDF
204.9 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2015-ENDM-VNS-CNP-PostPrint.pdf

Accesso aperto con embargo fino al 20/02/2017

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 444.5 kB
Formato Adobe PDF
444.5 kB Adobe PDF Visualizza/Apri

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/155351
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact