We design a flexible Evolutionary Framework for solving several classes of the Critical Node Problem (CNP), i.e. the maximal fragmentation of a graph through node deletion, given a measure of connectivity. The algorithm uses greedy rules in order to lead the search towards good quality solutions during reproduction and mutation phases. Such rules, which are only partially reported in the literature, are generalised and adapted to the six different formulations of the CNP considered along the paper. The link between solutions of different CNP formulations is investigated, both quantitatively and qualitatively. Furthermore, we provide a comparison with best known results when those are available in literature that confirms the good overall quality of our solutions.

A General Evolutionary Framework for different classes of Critical Node Problems

ARINGHIERI, ROBERTO;GROSSO, Andrea Cesare;HOSTEINS, Pierre;
2016-01-01

Abstract

We design a flexible Evolutionary Framework for solving several classes of the Critical Node Problem (CNP), i.e. the maximal fragmentation of a graph through node deletion, given a measure of connectivity. The algorithm uses greedy rules in order to lead the search towards good quality solutions during reproduction and mutation phases. Such rules, which are only partially reported in the literature, are generalised and adapted to the six different formulations of the CNP considered along the paper. The link between solutions of different CNP formulations is investigated, both quantitatively and qualitatively. Furthermore, we provide a comparison with best known results when those are available in literature that confirms the good overall quality of our solutions.
2016
55
128
145
http://www.sciencedirect.com/science/article/pii/S0952197616301191
Evolutionary algorithm, Critical Node Problem, Graph fragmentation, Greedy rules, Connectivity measures
Aringhieri, Roberto; Grosso, Andrea; Hosteins, Pierre; Scatamacchia, Rosario
File in questo prodotto:
File Dimensione Formato  
2016-EAAI-GA4CNPs-published.pdf

Accesso riservato

Descrizione: PDF editoriale
Tipo di file: PDF EDITORIALE
Dimensione 804.32 kB
Formato Adobe PDF
804.32 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2016-EAAI-GA4CNPs-PostPrint.pdf

Open Access dal 09/07/2018

Descrizione: Post print version
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 797.3 kB
Formato Adobe PDF
797.3 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: https://hdl.handle.net/2318/1583153
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 51
  • ???jsp.display-item.citation.isi??? 48
social impact