The DOI matches its Crossref record; 102 of the 102 references it cites were found in a registry or an index.
The Critical Node Detection Problem in networks: A survey
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Centrality in social networks conceptual clarification
Freeman, L. C. (1978) · Social Networks · doi:10.1016/0378-8733(78)90021-7 · Cited by 17,062
Grossman, P. (2009) · Discrete Mathematics for Computing · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,834
Karaboga, D., & Basturk, B. (2007) · Journal of Global Optimization · doi:10.1007/s10898-007-9149-x · Cited by 7,651
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (2000) · RePEc: Research Papers in Economics · Cited by 6,469
A faster algorithm for betweenness centrality*
Brandes, U. (2001) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.2001.9990249 · Cited by 4,936
The university of Florida sparse matrix collection
Davis, T. A., & Hu, Y. (2011) · ACM Transactions on Mathematical Software · doi:10.1145/2049662.2049663 · Cited by 3,630
Fellows, M. R. (2002) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(04)00301-9 · Cited by 2,836
Downey, R. G., & Fellows, M. R. (1999) · Monographs in Computer Science · doi:10.1007/978-1-4612-0515-9 · Cited by 2,532
Cost-effective outbreak detection in networks
Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281239 · Cited by 2,502
Resilience of the Internet to Random Breakdowns
Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.4626 · Cited by 2,391
Multiobjective evolutionary algorithms: A survey of the state of the art
Zhou, A., Qu, B.-Y., Li, H., Zhao, S.-Z., Suganthan, P. N., & Zhang, Q. (2011) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2011.03.001 · Cited by 2,255
The small-world phenomenon: an algorithmic perspective
Kleinberg, J. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335325 · Cited by 1,882
Complex Contagions and the Weakness of Long Ties
Centola, D., & Macy, M. (2007) · American Journal of Sociology · doi:10.1086/521848 · Cited by 1,878
(2010) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4419-1665-5 · Cited by 1,642
Schaeffer, S. E. (2007) · Computer Science Review · doi:10.1016/j.cosrev.2007.05.001 · Cited by 1,639
Graph minors. II. Algorithmic aspects of tree-width
Robertson, N., & Seymour, P. D. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90023-4 · Cited by 1,542
Clark, B. N., Colbourn, C. J., & Johnson, D. S. (1990) · Discrete Mathematics · doi:10.1016/0012-365x(90)90358-o · Cited by 1,429
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
A Separator Theorem for Planar Graphs
Lipton, R. J., & Tarjan, R. E. (1979) · SIAM Journal on Applied Mathematics · doi:10.1137/0136016 · Cited by 1,359
Immunization of complex networks
Pastor-Satorras, R., & Vespignani, A. (2002) · Physical Review E · doi:10.1103/physreve.65.036104 · Cited by 1,278
Networks formed from interdependent networks
Gao, J., Buldyrev, S. V., Stanley, H. E., & Havlin, S. (2012) · Nature Physics · doi:10.1038/nphys2180 · Cited by 1,216
Handbook of Combinatorial Optimization
(1999) · Springer eBooks · doi:10.1007/978-1-4757-3023-4 · Cited by 1,216
Identifying sets of key players in a social network
Borgatti, S. P. (2006) · Computational and Mathematical Organization Theory · doi:10.1007/s10588-006-7084-x · Cited by 1,174
Efficient Immunization Strategies for Computer Networks and Populations
Cohen, R., Havlin, S., & ben-Avraham, D. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.247901 · Cited by 1,162
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
Raghavan, P., & Tompson, C. D. (1987) · Combinatorica · doi:10.1007/bf02579324 · Cited by 1,010
Influential Nodes in a Diffusion Model for Social Networks
Kempe, D., Kleinberg, J., & Tardos, É. (2005) · Lecture Notes in Computer Science · doi:10.1007/11523468_91 · Cited by 948
Variable neighbourhood search: methods and applications
Hansen, P., Mladenović, N., & Moreno Pérez, J. A. (2010) · Annals of Operations Research · doi:10.1007/s10479-009-0657-6 · Cited by 860
Parshani, R., Buldyrev, S. V., & Havlin, S. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.048701 · Cited by 788
Protein–protein interactions define specificity in signal transduction
Pawson, T., & Nash, P. (2000) · Genes & Development · doi:10.1101/gad.14.9.1027 · Cited by 780
Rumors in a Network: Who's the Culprit?
Shah, D., & Zaman, T. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2158885 · Cited by 691
The Complexity of Multiterminal Cuts
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539792225297 · Cited by 662
On the hardness of approximating vertex cover
Dinur, I., & Safra, S. (2005) · Annals of Mathematics · doi:10.4007/annals.2005.162.439 · Cited by 636
Some simplified NP-complete problems
Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1974) · Proceedings of the sixth annual ACM symposium on Theory of computing - STOC '74 · doi:10.1145/800119.803884 · Cited by 614
INFOCOM, 2011 Proceedings IEEE
Lee, M., Hajjat, M. Y., Kompella, R. R., & Rao, S. J. K. (2011) · Cited by 577
Iterated Local Search: Framework and Applications
Lourenço, H. R., Martin, O. C., & Stützle, T. (2010) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4419-1665-5_12 · Cited by 571
Social Network Sensors for Early Detection of Contagious Outbreaks
Christakis, N. A., & Fowler, J. H. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012948 · Cited by 535
Robustness of interdependent networks under targeted attack
Huang, X., Gao, J., Buldyrev, S. V., Havlin, S., & Stanley, H. E. (2011) · Physical Review E · doi:10.1103/physreve.83.065101 · Cited by 527
Chartrand, G., & Zhang, P. (2004) · Cited by 525
The node-deletion problem for hereditary properties is NP-complete
Lewis, J. M., & Yannakakis, M. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90060-4 · Cited by 513
Recent Advances in Graph Partitioning
Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., & Schulz, C. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_4 · Cited by 482
Node-and edge-deletion NP-complete problems
Yannakakis, M. (1978) · Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 · doi:10.1145/800133.804355 · Cited by 435
Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks
Krause, A., Leskovec, J., Guestrin, C., VanBriesen, J., & Faloutsos, C. (2008) · Journal of Water Resources Planning and Management · doi:10.1061/(asce)0733-9496(2008)134:6(516 · Cited by 414
Locating the Source of Diffusion in Large-Scale Networks
Pinto, P. C., Thiran, P., & Vetterli, M. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.068702 · Cited by 409
Detecting critical nodes in sparse graphs
Arulselvan, A., Commander, C. W., Elefteriadou, L., & Pardalos, P. M. (2009) · Computers & Operations Research · doi:10.1016/j.cor.2008.08.016 · Cited by 381
Primal-dual approximation algorithms for integral flow and multicut in trees
Garg, N., Vazirani, V. V., & Yannakakis, M. (1997) · Algorithmica · doi:10.1007/bf02523685 · Cited by 378
Approximating Betweenness Centrality
Bader, D. A., Kintali, S., Madduri, K., & Mihail, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77004-6_10 · Cited by 340
Inferring the origin of an epidemic with a dynamic message-passing algorithm
Lokhov, A. Y., Mézard, M., Ohta, H., & Zdeborová, L. (2014) · Physical Review E · doi:10.1103/physreve.90.012801 · Cited by 322
Krebs, V. (2002) · First Monday · doi:10.5210/fm.v7i4.941 · Cited by 313
Node-Deletion Problems on Bipartite Graphs
Yannakakis, M. (1981) · SIAM Journal on Computing · doi:10.1137/0210022 · Cited by 306
Detecting Critical Nodes in Interdependent Power Networks for Vulnerability Assessment
Nguyen, D. T., Shen, Y., & Thai, M. T. (2013) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2012.2229398 · Cited by 279
Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
Khot, S. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539705447037 · Cited by 236
GRASP with Path-Relinking: Recent Advances and Applications
Resendel, M. G. C., & Ribeiro, C. C. (2005) · Springer eBooks · doi:10.1007/0-387-25383-1_2 · Cited by 226
APID: Agile Protein Interaction DataAnalyzer
Prieto, C., & De Las Rivas, J. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkl128 · Cited by 224
Comparative Approaches for Assessing Network Vulnerability
Grubesic, T. H., Matisziw, T. C., Murray, A. T., & Snediker, D. (2008) · International Regional Science Review · doi:10.1177/0160017607308679 · Cited by 193
Characterization of Protein–Protein Interfaces
Yan, C., Wu, F., Jernigan, R. L., Dobbs, D., & Honavar, V. (2008) · The Protein Journal · doi:10.1007/s10930-007-9108-x · Cited by 190
Festa, P., Pardalos, P. M., & Resende, M. G. C. (1999) · Springer eBooks · doi:10.1007/978-1-4757-3023-4_4 · Cited by 182
Textbook of Drug Design and Discovery
(2016) · CRC Press eBooks · doi:10.1201/9781315371818 · Cited by 175
Epidemic dynamics on complex networks*
Tao, Z., Zhongqian, F., & Binghong, W. (2006) · Progress in Natural Science · doi:10.1080/10020070612330019 · Cited by 159
Graph Partitioning Algorithms with Applications to Scientific Computing
Pothen, A. (1997) · ICASE/LaRC interdisciplinary series in science and engineering · doi:10.1007/978-94-011-5412-3_12 · Cited by 157
Automata, Languages and Programming
Bugliesi, M., Wegener, I., Sassone, V., & Preneel, B. (2006) · Lecture notes in computer science · doi:10.1007/11787006 · Cited by 152
Hardness of approximating problems on cubic graphs
Alimonti, P., & Kann, V. (1997) · Lecture notes in computer science · doi:10.1007/3-540-62592-5_80 · Cited by 146
On the Discovery of Critical Links and Nodes for Assessing Network Vulnerability
Shen, Y., Nguyen, N. P., Ying, X., & Thai, M. T. (2012) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2012.2215882 · Cited by 144
Identification of Protein Interactions Involved in Cellular Signaling
Westermarck, J., Ivaska, J., & Corthals, G. L. (2013) · Molecular & Cellular Proteomics · doi:10.1074/mcp.r113.027771 · Cited by 143
Proceedings of the 20th international conference companion on World wide web
Sadagopan, S., Ramamritham, K., Kumar, A., Ravindra, M. P., Bertino, E., & Kumar, R. (2011) · Cited by 127
Exact interdiction models and algorithms for disconnecting networks via node deletions
Shen, S., Smith, J. C., & Goli, R. (2012) · Discrete Optimization · doi:10.1016/j.disopt.2012.07.001 · Cited by 125
Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion
Ronoh, N. (2016) · doi:10.1145/2908961 · Cited by 120
Proceedings of the thirty-second annual ACM symposium on Theory of computing
(2000) · doi:10.1145/335305 · Cited by 117
Exact identification of critical nodes in sparse networks via new compact formulations
Veremyev, A., Boginski, V. L., & Pasiliao, E. L. (2013) · Optimization Letters · doi:10.1007/s11590-013-0666-x · Cited by 109
Critical nodes for distance‐based connectivity and related problems in graphs
Veremyev, A., Prokopyev, O. A., & Pasiliao, E. L. (2015) · Networks · doi:10.1002/net.21622 · Cited by 108
Shen, S., & Smith, J. C. (2011) · Networks · doi:10.1002/net.20464 · Cited by 102
Ventresca, M. (2012) · Computers & Operations Research · doi:10.1016/j.cor.2012.02.008 · Cited by 102
Textbook of Drug Design and Discovery
Smith, H. J., & Williams, H. J. (2002) · CRC Press eBooks · doi:10.1201/b12381 · Cited by 98
Blocking Simple and Complex Contagion by Edge Removal
Kuhlman, C. J., Tuli, G., Swarup, S., MARATHE, M. V., & Ravi, S. S. (2013) · Proceedings · doi:10.1109/icdm.2013.47 · Cited by 94
Minimal multicut and maximal integer multiflow: A survey
Costa, M.-C., Létocart, L., & Roupin, F. (2004) · European Journal of Operational Research · doi:10.1016/j.ejor.2003.10.037 · Cited by 94
Addis, B., Summa, M. D., & Grosso, A. (2013) · Discrete Applied Mathematics · doi:10.1016/j.dam.2013.03.021 · Cited by 87
Node-Deletion NP-Complete Problems
Krishnamoorthy, M. S., & Deo, N. (1979) · SIAM Journal on Computing · doi:10.1137/0208049 · Cited by 81
A general Evolutionary Framework for different classes of Critical Node Problems
Aringhieri, R., Grosso, A., Hosteins, P., & Scatamacchia, R. (2016) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2016.06.010 · Cited by 78
Optimizing network attacks by artificial bee colony
Lozano, M., García‐Martínez, C., Rodríguez, F. J., & Trujillo, H. M. (2016) · Information Sciences · doi:10.1016/j.ins.2016.10.014 · Cited by 77
Proceedings of the tenth annual ACM symposium on Theory of computing
Lipton, R. J., Burkhard, W. A., Savitch, W. J., Friedman, E. P., & Aho, A. (1978) · Cited by 71
A derandomized approximation algorithm for the critical node detection problem
Ventresca, M., & Aleman, D. M. (2013) · Computers & Operations Research · doi:10.1016/j.cor.2013.09.012 · Cited by 69
Network Under Joint Node and Link Attacks: Vulnerability Assessment Methods and Analysis
Dinh, T. N., & Thai, M. T. (2014) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2014.2317486 · Cited by 62
Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
Cälinescu, G., Fernandes, C. G., & Reed, B. A. (2003) · Journal of Algorithms · doi:10.1016/s0196-6774(03)00073-7 · Cited by 58
Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks
Fan, N., & Pardalos, P. M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17458-2_15 · Cited by 48
Finding critical nodes in infrastructure networks
Faramondi, L., Setola, R., Panzieri, S., Pascucci, F., & Oliva, G. (2017) · International Journal of Critical Infrastructure Protection · doi:10.1016/j.ijcip.2017.11.004 · Cited by 47
Proceedings of the sixth annual ACM symposium on Theory of computing
Constable, R. L., Ritchie, R. W., Carlyle, J. W., & Harrison, M. A. (1974) · Cited by 44
Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
Guo, J., Hüffner, F., Kenar, E., Niedermeier, R., & Uhlmann, J. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2007.02.014 · Cited by 40
The multi-multiway cut problem
Avidor, A., & Langberg, M. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.02.026 · Cited by 39
Finding Critical Nodes for Inhibiting Diffusion of Complex Contagions in Social Networks
Kuhlman, C. J., Kumar, V. S. A., MARATHE, M. V., Ravi, S. S., & Rosenkrantz, D. J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15883-4_8 · Cited by 37
Algorithms and Models for the Web-Graph
Hutchison, D., Weikum, G., Vardi, M. Y., Tygar, D., Terzopoulos, D., Sudan, M., Steffen, B., Rangan, C. P., Nierstrasz, O., Naor, M., et al. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78808-9 · Cited by 35
A randomized algorithm with local search for containment of pandemic disease spread
Ventresca, M., & Aleman, D. M. (2014) · Computers & Operations Research · doi:10.1016/j.cor.2014.02.003 · Cited by 29
Node Removal in Criminal Networks
Petersen, R. R., Rhodes, C. J., & Wiil, U. K. (2011) · European Intelligence and Security Informatics Conference · doi:10.1109/eisic.2011.57 · Cited by 25
Studying Connectivity Properties in Human Protein–Protein Interaction Network in Cancer Pathway
Tomaino, V., Arulselvan, A., Veltri, P., & Pardalos, P. M. (2012) · Springer optimization and its applications · doi:10.1007/978-1-4614-2107-8_10 · Cited by 24
A Fast Greedy Algorithm for the Critical Node Detection Problem
Ventresca, M., & Aleman, D. M. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-12691-3_45 · Cited by 20
On the Computational Complexity of Vertex Integrity and Component Order Connectivity
Drange, P. G., Dregi, M. S., & Hof, P. V. ’. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-13075-0_23 · Cited by 19
Covertness Centrality in Networks
Ovelgönne, M., Kang, C., Sawant, A., & Subrahmanian, V. S. (2012) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2012.156 · Cited by 18
Faramondi, L., Oliva, G., Setola, R., Pascucci, F., Amideo, A. E., & Scaparra, M. P. (2017) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-319-67308-0_32 · Cited by 13
Least Squares Method for Diffusion Source Localization in Complex Networks
Lalou, M., & Kheddouci, H. (2016) · Studies in computational intelligence · doi:10.1007/978-3-319-50901-3_38 · Cited by 10
Self-citationNetwork vulnerability assessment under cascading failures
Shen, Y., & Thai, M. T. (2013) · Globecom · doi:10.1109/glocom.2013.6831290 · Cited by 6
Research works printed but not linked: 54
- Corley, 1982, Most vital links and nodes in weighted networks, Oper. Res. Lett., 1, 157, 10.1016/0167-6377(82)90020-7 · doi:10.1016/0167-6377(82)90020-7
- Hellwig, 2008, Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Discrete Math., 308, 3265, 10.1016/j.disc.2007.06.035 · DOI
- Goldschmidt, 1994, A polynomial algorithm for the k-cut problem for fixed k, Math. Oper. Res., 19, 24, 10.1287/moor.19.1.24 · doi:10.1287/moor.19.1.24
- He, 1991, An improved algorithm for the planar 3-cut problem, J. Algorithms, 12, 23, 10.1016/0196-6774(91)90021-P · doi:10.1016/0196-6774(91)90021-p
- Guo, 2005, Fixed-parameter tractability and data reduction for multicut in trees, Networks, 46, 124, 10.1002/net.20081 · doi:10.1002/net.20081
- Chopra, 1991, On the multiway cut polyhedron, Networks, 21, 51, 10.1002/net.3230210106 · doi:10.1002/net.3230210106
- Chopra, 1996, Extended formulations for the A-cut problem, Math. Program., 73, 7, 10.1007/BF02592096 · doi:10.1007/bf02592096
- Bui, 1992, Finding good approximate vertex and edge partitions is NP-hard, Inform. Process. Lett., 42, 153, 10.1016/0020-0190(92)90140-Q · doi:10.1016/0020-0190(92)90140-q
- Fukuyama, 2006, NP-completeness of the planar separator problems, J. Graph Algorithms Appl., 10, 317, 10.7155/jgaa.00130 · doi:10.7155/jgaa.00130
- de Souza, 2005, The vertex separator problem: algorithms and computations, Math. Program., 103, 609, 10.1007/s10107-005-0573-8 · doi:10.1007/s10107-005-0573-8
- Biha, 2011, An exact algorithm for solving the vertex separator problem, J. Global Optim., 49, 425, 10.1007/s10898-010-9568-y · doi:10.1007/s10898-010-9568-y
- U. Benlic, J.-K. Hao, Breakout local search for the vertex separator problem, in: IJCAI, 2013, pp. 461–467.
- Chen, 2009, An improved parameterized algorithm for the minimum node multiway cut problem, Algorithmica, 55, 1, 10.1007/s00453-007-9130-6 · doi:10.1007/s00453-007-9130-6
- Papadopoulos, 2012, Restricted vertex multicut on permutation graphs, Discrete Appl. Math., 160, 1791, 10.1016/j.dam.2012.03.021 · doi:10.1016/j.dam.2012.03.021
- Marx, 2006, Parameterized graph separation problems, Theoret. Comput. Sci., 351, 394, 10.1016/j.tcs.2005.10.007 · doi:10.1016/j.tcs.2005.10.007
- Boginski, 2009, Identifying critical nodes in protein–protein interaction networks, Clustering Challenges Biol. Netw., 153, 10.1142/9789812771667_0007 · doi:10.1142/9789812771667_0007
- Jungck, 1982, Computer-assisted sequencing, interval graphs, and molecular evolution, Biosystems, 15, 259, 10.1016/0303-2647(82)90010-7 · doi:10.1016/0303-2647(82)90010-7
- Pal, 2009, Interval tree and its applications, Adv. Model. Optim., 11, 211
- Bodlaender, 1994, A tourist guide through treewidth, Acta Cybernet., 11, 1
- Bodlaender, 2006, Treewidth: characterizations, applications, and computations, WG, 4271, 1
- Khachiyan, 2008, On short paths interdiction problems: total and node-wise limited interdiction, Theory Comput. Syst., 43, 204, 10.1007/s00224-007-9025-6 · DOI
- Choi, 1989, Graph bipartization and via minimization, SIAM J. Discrete Math., 2, 38, 10.1137/0402004 · doi:10.1137/0402004
- Marx, 2010, Chordal deletion is fixed-parameter tractable, Algorithmica, 57, 747, 10.1007/s00453-008-9233-8 · doi:10.1007/s00453-008-9233-8
- Marx, 2012, Obtaining a planar graph by vertex deletion, Algorithmica, 62, 807, 10.1007/s00453-010-9484-z · doi:10.1007/s00453-010-9484-z
- Berger, 2014, Complexity and approximability of the k-way vertex cut, Networks, 63, 170, 10.1002/net.21534 · doi:10.1002/net.21534
- Di Summa, 2011, Complexity of the critical node problem over trees, Comput. Oper. Res., 38, 1766, 10.1016/j.cor.2011.02.016 · doi:10.1016/j.cor.2011.02.016
- Lalou, 2016, Component-cardinality-constrained critical node problem in graphs, Discrete Appl. Math., 210, 150, 10.1016/j.dam.2015.01.043 · doi:10.1016/j.dam.2015.01.043
- Di Summa, 2012, Branch and cut algorithms for detecting critical nodes in undirected graphs, Comput. Optim. Appl., 53, 649, 10.1007/s10589-012-9458-y · doi:10.1007/s10589-012-9458-y
- Oosten, 2007, Disconnecting graphs by removing vertices: a polyhedral approach, Stat. Neerl., 61, 35, 10.1111/j.1467-9574.2007.00350.x · doi:10.1111/j.1467-9574.2007.00350.x
- Veremyev, 2014, An integer programming framework for critical elements detection in graphs, J. Combin. Optim., 28, 233, 10.1007/s10878-014-9730-4 · DOI
- Aringhieri, 2015, VNS solutions for the critical node problem, Electron. Notes Discrete Math., 47, 37, 10.1016/j.endm.2014.11.006 · doi:10.1016/j.endm.2014.11.006
- Addis, 2016, Hybrid constructive heuristics for the critical node problem, Ann. Oper. Res., 238, 637, 10.1007/s10479-016-2110-y · doi:10.1007/s10479-016-2110-y
- Aringhieri, 2016, Local search metaheuristics for the critical node problem, Networks, 67, 209, 10.1002/net.21671 · doi:10.1002/net.21671
- Pullan, 2015, Heuristic identification of critical nodes in sparse real-world graphs, J. Heuristics, 21, 577, 10.1007/s10732-015-9290-5 · doi:10.1007/s10732-015-9290-5
- Purevsuren, 2016, Heuristic algorithm for identifying critical nodes in graphs, Adv. Comput. Sci.: Int. J., 5, 1
- Balas, 2005, The vertex separator problem: a polyhedral investigation, Math. Program., 103, 583, 10.1007/s10107-005-0574-7 · doi:10.1007/s10107-005-0574-7
- Ventresca, 2018, The bi-objective critical node detection problem, European J. Oper. Res., 265, 895, 10.1016/j.ejor.2017.08.053 · doi:10.1016/j.ejor.2017.08.053
- Wood, 1993, Deterministic network interdiction, Math. Comput. Modelling, 17, 1, 10.1016/0895-7177(93)90236-R · doi:10.1016/0895-7177(93)90236-r
- Myung, 2004, A cutting plane algorithm for computing k-edge survivability of a network, European J. Oper. Res., 156, 579, 10.1016/S0377-2217(03)00135-8 · doi:10.1016/s0377-2217(03)00135-8
- Purevsuren, 2017, Hybridization of GRASP with exterior path relinking for identifying critical nodes in graphs, IAENG Int. J. Comput. Sci., 44
- Glover, 2014, Exterior path relinking for zero-one optimization, Int. J. Appl. Metaheuristic Comput., 5, 1, 10.4018/ijamc.2014070101 · doi:10.4018/ijamc.2014070101
- Y. Zhou, J.-K. Hao, F. Glover, Memetic search for identifying critical nodes in sparse graphs, 2017. ArXiv Preprint arXiv:1705.04119. · arXiv
- Moscato, 2002, Memetic algorithms, Handb. Appl. Optim., 157, 168
- Aringhieri, 2016, A preliminary analysis of the distance based critical node problem, Electron. Notes Discrete Math., 55, 25, 10.1016/j.endm.2016.10.007 · doi:10.1016/j.endm.2016.10.007
- Aringhieri, 2018, Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem, Discrete Appl. Math., 10.1016/j.dam.2017.12.035 · doi:10.1016/j.dam.2017.12.035
- Barefoot, 1987, Vulnerability in graphs -a comparative survey, J. Combin. Math. Combin. Comput., 1, 13
- Bagga, 1992, A survey of integrity, Discrete Appl. Math., 37, 13, 10.1016/0166-218X(92)90122-Q · doi:10.1016/0166-218x(92)90122-q
- Balas, 1989, On graphs with polynomially solvable maximum-weight clique problem, Networks, 19, 247, 10.1002/net.3230190206 · doi:10.1002/net.3230190206
- Gavril, 2000, Maximum weight independent sets and cliques in intersection graphs of filaments, Inform. Process. Lett., 73, 181, 10.1016/S0020-0190(00)00025-9 · doi:10.1016/s0020-0190(00)00025-9
- Hayward, 1985, Weakly triangulated graphs, J. Combin. Theory Ser. B, 39, 200, 10.1016/0095-8956(85)90050-4 · doi:10.1016/0095-8956(85)90050-4
- Xiao, 2010, Simple and improved parameterized algorithms for multiterminal cuts, Theory Comput. Syst., 46, 723, 10.1007/s00224-009-9215-5 · doi:10.1007/s00224-009-9215-5
- Commander, 2007, The wireless network jamming problem, J. Combin. Optim., 14, 481, 10.1007/s10878-007-9071-7 · doi:10.1007/s10878-007-9071-7
- Fan, 2011, Economic analysis of the N- k power grid contingency selection and evaluation by graph algorithms and interdiction methods, Energy Syst., 2, 313, 10.1007/s12667-011-0038-5 · doi:10.1007/s12667-011-0038-5
- Vitoriano, 2011, A multi-criteria optimization model for humanitarian aid distribution, J. Global Optim., 51, 189, 10.1007/s10898-010-9603-z · doi:10.1007/s10898-010-9603-z
Cited by
An Evolutionary Algorithm for Large-Scale Sparse Multiobjective Optimization Problems
Tian, Y., Zhang, X., Wang, C., & Jin, Y. (2020) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2019.2918140 · Cited by 440
Finding key players in complex networks through deep reinforcement learning
Fan, C., Zeng, L., Sun, Y., & Liu, Y.-Y. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-020-0177-2 · Cited by 425
Evolutionary Large-Scale Multi-Objective Optimization: A Survey
Tian, Y., Si, L., Zhang, X., Cheng, R., He, C., Tan, K. C., & Jin, Y. (2022) · ACM Computing Surveys · doi:10.1145/3470971 · Cited by 401
Faheem, M., Shah, S. B. H., Butt, R. A., Raza, B., Anwar, M., Ashraf, M. W., Ngadi, M. A., & Gungor, V. C. (2018) · Computer Science Review · doi:10.1016/j.cosrev.2018.08.001 · Cited by 392
Camacho, D., Panizo-LLedot, Á., Bello-Orgaz, G., Gonzalez-Pardo, A., & Cambria, E. (2020) · Information Fusion · doi:10.1016/j.inffus.2020.05.009 · Cited by 329
Metadata
- Authors
- Lalou, M., Tahraoui, M. A., & Kheddouci, H.
- Venue
- Computer Science Review
- Publisher
- Elsevier BV
- Published
- 2018-05
- Volume
- 28
- Pages
- 92-117
- ISSN
- 1574-0137 (ISSN-L)
- OpenAlex
- W2792824988
- Cited by
- 311
- References
- 102
- FWCI
- 15.62
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.