Computing Critical Nodes in Directed Graphs
Open Access
- 18 July 2018
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 23 (2) , 1-24
Abstract
We consider the critical node detection problem (CNDP) in directed graphs, which can be defined as follows. Given a directed graph G and a parameter k , we wish to remove a subset S of at most k vertices of G 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.Keywords
Funding Information
- Italian Ministry of Education, University and Research
- AMANDA
This publication has 18 references indexed in Scilit:
- Finding strong bridges and strong articulation points in linear timeTheoretical Computer Science, 2012
- Detecting critical nodes in sparse graphsComputers & Operations Research, 2009
- Linear-Time Algorithms for Dominators and Other Path-Evaluation ProblemsSIAM Journal on Computing, 2008
- Inoculation strategies for victims of viruses and the sum-of-squares partition problemJournal of Computer and System Sciences, 2006
- Finding Dominators in PracticeJournal of Graph Algorithms and Applications, 2006
- Efficient Immunization Strategies for Computer Networks and PopulationsPhysical Review Letters, 2003
- Dominators in Linear TimeSIAM Journal on Computing, 1999
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991
- Finding Dominators in Directed GraphsSIAM Journal on Computing, 1974
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972