We consider the critical node detection problem (CNDP) in directed graphs. 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 n S has minimum pairwise strong connectivity. This problem is NP-hard, and thus we are interested in practical heuristics. We present a sophisticated linear-time algorithm for the k = 1 case, and, based on this algorithm, give 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.
Paudel, N., Georgiadis, L., Italiano, G.f. (2017). Computing critical nodes in directed graphs. In Proceedings of the Workshop on Algorithm Engineering and Experiments (pp.43-57). Society for Industrial and Applied Mathematics Publications.
Computing critical nodes in directed graphs
Italiano, Giuseppe F.
2017-01-01
Abstract
We consider the critical node detection problem (CNDP) in directed graphs. 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 n S has minimum pairwise strong connectivity. This problem is NP-hard, and thus we are interested in practical heuristics. We present a sophisticated linear-time algorithm for the k = 1 case, and, based on this algorithm, give 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
