We consider the critical node detection problem (CNDP) in directed graphs, which can be defined as follows. Given a directed graphG and a parameter k, we wish to remove a subset S of at most k vertices ofG such that the residual graph G\S has minimum pairwise strong connectivity. This problem is NP-hard, and thus we are interested in practical heuristics. In this article, we apply the framework of Georgiadis et al. (SODA 2017) and provide a sophisticated linear-time algorithm for the k = 1 case. Based on this algorithm, we provide an efficient heuristic for the general case. Then, we conduct a thorough experimental evaluation of various heuristics for CNDP. Our experimental results suggest that our heuristic performs very well in practice, both in terms of running time and of solution quality.

Computing critical nodes in directed graphs / Paudel, Nilakantha; Georgiadis, Loukas; Italiano, Giuseppe Francesco. - In: ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS. - ISSN 1084-6654. - 23:1(2018), pp. 1-24. [10.1145/3228332]

Computing critical nodes in directed graphs

Italiano, Giuseppe F.
2018

Abstract

We consider the critical node detection problem (CNDP) in directed graphs, which can be defined as follows. Given a directed graphG and a parameter k, we wish to remove a subset S of at most k vertices ofG such that the residual graph G\S has minimum pairwise strong connectivity. This problem is NP-hard, and thus we are interested in practical heuristics. In this article, we apply the framework of Georgiadis et al. (SODA 2017) and provide a sophisticated linear-time algorithm for the k = 1 case. Based on this algorithm, we provide an efficient heuristic for the general case. Then, we conduct a thorough experimental evaluation of various heuristics for CNDP. Our experimental results suggest that our heuristic performs very well in practice, both in terms of running time and of solution quality.
2018
Combinatorial optimization; Critical nodes; Directed graphs; NP-hard; Strong articulation points; Strong connectivity; Theoretical Computer Science
Computing critical nodes in directed graphs / Paudel, Nilakantha; Georgiadis, Loukas; Italiano, Giuseppe Francesco. - In: ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS. - ISSN 1084-6654. - 23:1(2018), pp. 1-24. [10.1145/3228332]
File in questo prodotto:
File Dimensione Formato  
a2-paudel.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM (Digital rights management) non definiti
Dimensione 1.4 MB
Formato Adobe PDF
1.4 MB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

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/11385/182822
Citazioni
  • Scopus 12
  • ???jsp.display-item.citation.isi??? ND
social impact