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.
2019
253
103
121
https://www.sciencedirect.com/science/article/pii/S0166218X18300039
Connectivity measure; Critical Node Problem; Dynamic programming; Polynomial time algorithms; Shortest paths; Discrete Mathematics and Combinatorics; Applied Mathematics
Aringhieri, Roberto; Grosso, Andrea; Hosteins, Pierre*; Scatamacchia, Rosario
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.

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