We study the Distance Critical Node Problem, a generalisation of the Critical Node Problem where the distances between node pairs impact on the objective function. We establish complexity results for the problem according to specific distance functions and provide polynomial and pseudo-polynomial algorithms for special graph classes such as paths, trees and series–parallel graphs. We also provide additional insights about special cases of the Critical Node Problem variants already tackled in the literature.
Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem
Aringhieri, Roberto;Grosso, Andrea;Hosteins, Pierre;Scatamacchia, Rosario
2019-01-01
Abstract
We study the Distance Critical Node Problem, a generalisation of the Critical Node Problem where the distances between node pairs impact on the objective function. We establish complexity results for the problem according to specific distance functions and provide polynomial and pseudo-polynomial algorithms for special graph classes such as paths, trees and series–parallel graphs. We also provide additional insights about special cases of the Critical Node Problem variants already tackled in the literature.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
2018-DCNP-DAM-postPrint.pdf
Open Access dal 03/02/2020
Descrizione: post print version
Tipo di file:
POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione
583.92 kB
Formato
Adobe PDF
|
583.92 kB | Adobe PDF | Visualizza/Apri |
2019-DCNP-DAM-pubished.pdf
Accesso riservato
Descrizione: PDF editoriale
Tipo di file:
PDF EDITORIALE
Dimensione
460.65 kB
Formato
Adobe PDF
|
460.65 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.