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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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 networksPreprint
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (2000) · Cited by 6,467
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
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:10.1016/j.disc.2007.06.035
- 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:10.1007/s00224-007-9025-6
- 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:10.1007/s10878-014-9730-4
- 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
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
Tian, Y., Lu, C., Zhang, X., Tan, K. C., & Jin, Y. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.2979930 · Cited by 318
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The Critical Node Detection Problem in networks: A survey. https://app.cochat.ai/papers/10.1016/j.cosrev.2018.02.002
- The paper
- Lalou, M., Tahraoui, M. A., & Kheddouci, H. (2018). The Critical Node Detection Problem in networks: A survey. Computer Science Review. https://doi.org/10.1016/j.cosrev.2018.02.002
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.