{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:33:23Z","timestamp":1787510003109,"version":"build-2736575974"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,7,18]],"date-time":"2018-07-18T00:00:00Z","timestamp":1531872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Italian Ministry of Education, University and Research"},{"name":"AMANDA"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:p>\n                    We consider the critical node detection problem (CNDP) in directed graphs, which can be defined as follows. Given a directed graph\n                    <jats:italic>G<\/jats:italic>\n                    and a parameter\n                    <jats:italic>k<\/jats:italic>\n                    , we wish to remove a subset\n                    <jats:italic>S<\/jats:italic>\n                    of at most\n                    <jats:italic>k<\/jats:italic>\n                    vertices of\n                    <jats:italic>G<\/jats:italic>\n                    such that the residual graph\n                    <jats:italic>G<\/jats:italic>\n                    \u2216\n                    <jats:italic>S<\/jats:italic>\n                    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.\u00a0(SODA 2017) and provide a sophisticated linear-time algorithm for the\n                    <jats:italic>k<\/jats:italic>\n                    =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.\n                  <\/jats:p>","DOI":"10.1145\/3228332","type":"journal-article","created":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T09:25:21Z","timestamp":1531733121000},"page":"1-24","source":"Crossref","is-referenced-by-count":13,"title":["Computing Critical Nodes in Directed Graphs"],"prefix":"10.1145","volume":"23","author":[{"given":"Nilakantha","family":"Paudel","sequence":"first","affiliation":[{"name":"University of Rome Tor Vergata, Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Loukas","family":"Georgiadis","sequence":"additional","affiliation":[{"name":"University of Ioannina, Ioannina, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[{"name":"University of Rome Tor Vergata, Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317263"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.08.016"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"A.-L. Barab\u00e1si and R. Albert. 1999. Emergence of scaling in random networks. Science 286 5439 (1999) 509--512.  A.-L. Barab\u00e1si and R. Albert. 1999. Emergence of scaling in random networks. Science 286 5439 (1999) 509--512.","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_5_1","first-page":"163","article-title":"A faster algorithm for betweenness centrality","volume":"25","author":"Brandes U.","year":"2001","unstructured":"U. Brandes . 2001 . A faster algorithm for betweenness centrality . J. Sociol. 25 , 2 (2001), 163 -- 177 . arXiv:http:\/\/dx.doi.org\/10.1080\/0022250X.2001.9990249 10.1080\/0022250X.2001.9990249 U. Brandes. 2001. A faster algorithm for betweenness centrality. J. Sociol. 25, 2 (2001), 163--177. arXiv:http:\/\/dx.doi.org\/10.1080\/0022250X.2001.9990249","journal-title":"J. Sociol."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070693217"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.247901"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_9_1","unstructured":"C. Demetrescu A. V. Goldberg and D. S. Johnson. 2007. 9th DIMACS Implementation Challenge: Shortest Paths. Retrieved from http:\/\/www.dis.uniroma1.it\/challenge9\/.  C. Demetrescu A. V. Goldberg and D. S. Johnson. 2007. 9th DIMACS Implementation Challenge: Shortest Paths. Retrieved from http:\/\/www.dis.uniroma1.it\/challenge9\/."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2170849"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2542182.2542192"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2968448"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms. 1880--1899","author":"Georgiadis L.","unstructured":"L. Georgiadis , G. F. Italiano , and N. Parotsidis . 2017. Strong connectivity in directed graphs under failures . In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms. 1880--1899 . L. Georgiadis, G. F. Italiano, and N. Parotsidis. 2017. Strong connectivity in directed graphs under failures. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms. 1880--1899."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00119"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915)","author":"Henzinger M.","unstructured":"M. Henzinger , S. Krinninger , and V. Loitzenbauer . 2015. Finding 2-edge and 2-vertex strongly connected components in quadratic time . In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915) . 713--724. M. Henzinger, S. Krinninger, and V. Loitzenbauer. 2015. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915). 713--724."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.11.011"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_18_1","volume-title":"Uncloaking terrorist networks. First Monday 7, 4","author":"Krebs V.","year":"2002","unstructured":"V. Krebs . 2002. Uncloaking terrorist networks. First Monday 7, 4 ( 2002 ). V. Krebs. 2002. Uncloaking terrorist networks. First Monday 7, 4 (2002)."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2010 European Conference on Machine Learning and Knowledge Discovery in Databases: Part II (ECML PKDD\u201910)","author":"Kuhlman C. J.","unstructured":"C. J. Kuhlman , V. S. Anil Kumar , M. V. Marathe , S. S. Ravi , and D. J. Rosenkrantz . 2010. Finding critical nodes for inhibiting diffusion of complex contagions in social networks . In Proceedings of the 2010 European Conference on Machine Learning and Knowledge Discovery in Databases: Part II (ECML PKDD\u201910) . Springer-Verlag, Berlin, 111--127. C. J. Kuhlman, V. S. Anil Kumar, M. V. Marathe, S. S. Ravi, and D. J. Rosenkrantz. 2010. Finding critical nodes for inhibiting diffusion of complex contagions in social networks. In Proceedings of the 2010 European Conference on Machine Learning and Knowledge Discovery in Databases: Part II (ECML PKDD\u201910). Springer-Verlag, Berlin, 111--127."},{"key":"e_1_2_1_20_1","unstructured":"J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data.  J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_21_1","first-page":"1999","article-title":"The PageRank Citation Ranking: Bringing Order to the Web","author":"Page L.","year":"1999","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . 1999 . The PageRank Citation Ranking: Bringing Order to the Web . Technical Report 1999 - 1966 . Stanford InfoLab. L. Page, S. Brin, R. Motwani, and T. Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report 1999-66. Stanford InfoLab.","journal-title":"Technical Report"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX\u201917)","author":"Paudel N.","unstructured":"N. Paudel , L. Georgiadis , and G. F. Italiano . 2017. Computing critical nodes in directed graphs . In Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX\u201917) . 43--57. N. Paudel, L. Georgiadis, and G. F. Italiano. 2017. Computing critical nodes in directed graphs. In Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX\u201917). 43--57."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2215882"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203006"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268499"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40649-015-0010-y"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3228332","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3228332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:07:34Z","timestamp":1750198054000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3228332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,18]]},"references-count":27,"alternative-id":["10.1145\/3228332"],"URL":"https:\/\/doi.org\/10.1145\/3228332","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,18]]}}}