Student or educator? Sign up with your school email and get 6 months of Pro free.
Cited by 311

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

Lalou, Mohammed, Tahraoui, Mohammed Amin, Kheddouci, Hamamache·2018·Computer Science Review

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1016/j.cosrev.2018.02.002

Cites

102 of 102 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 102 references

Research works printed but not linked: 54

  1. 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
  2. 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
  3. 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
  4. 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
  5. Guo, 2005, Fixed-parameter tractability and data reduction for multicut in trees, Networks, 46, 124, 10.1002/net.20081 · doi:10.1002/net.20081
  6. Chopra, 1991, On the multiway cut polyhedron, Networks, 21, 51, 10.1002/net.3230210106 · doi:10.1002/net.3230210106
  7. Chopra, 1996, Extended formulations for the A-cut problem, Math. Program., 73, 7, 10.1007/BF02592096 · doi:10.1007/bf02592096
  8. 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
  9. Fukuyama, 2006, NP-completeness of the planar separator problems, J. Graph Algorithms Appl., 10, 317, 10.7155/jgaa.00130 · doi:10.7155/jgaa.00130
  10. 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
  11. 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
  12. U. Benlic, J.-K. Hao, Breakout local search for the vertex separator problem, in: IJCAI, 2013, pp. 461–467.
  13. 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
  14. 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
  15. 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
  16. Boginski, 2009, Identifying critical nodes in protein–protein interaction networks, Clustering Challenges Biol. Netw., 153, 10.1142/9789812771667_0007 · doi:10.1142/9789812771667_0007
  17. 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
  18. Pal, 2009, Interval tree and its applications, Adv. Model. Optim., 11, 211
  19. Bodlaender, 1994, A tourist guide through treewidth, Acta Cybernet., 11, 1
  20. Bodlaender, 2006, Treewidth: characterizations, applications, and computations, WG, 4271, 1
  21. 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
  22. Choi, 1989, Graph bipartization and via minimization, SIAM J. Discrete Math., 2, 38, 10.1137/0402004 · doi:10.1137/0402004
  23. Marx, 2010, Chordal deletion is fixed-parameter tractable, Algorithmica, 57, 747, 10.1007/s00453-008-9233-8 · doi:10.1007/s00453-008-9233-8
  24. 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
  25. Berger, 2014, Complexity and approximability of the k-way vertex cut, Networks, 63, 170, 10.1002/net.21534 · doi:10.1002/net.21534
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. Aringhieri, 2016, Local search metaheuristics for the critical node problem, Networks, 67, 209, 10.1002/net.21671 · doi:10.1002/net.21671
  34. 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
  35. Purevsuren, 2016, Heuristic algorithm for identifying critical nodes in graphs, Adv. Comput. Sci.: Int. J., 5, 1
  36. 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
  37. 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
  38. 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
  39. 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
  40. Purevsuren, 2017, Hybridization of GRASP with exterior path relinking for identifying critical nodes in graphs, IAENG Int. J. Comput. Sci., 44
  41. 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
  42. Y. Zhou, J.-K. Hao, F. Glover, Memetic search for identifying critical nodes in sparse graphs, 2017. ArXiv Preprint arXiv:1705.04119. · arXiv
  43. Moscato, 2002, Memetic algorithms, Handb. Appl. Optim., 157, 168
  44. 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
  45. 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
  46. Barefoot, 1987, Vulnerability in graphs -a comparative survey, J. Combin. Math. Combin. Comput., 1, 13
  47. 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
  48. Balas, 1989, On graphs with polynomially solvable maximum-weight clique problem, Networks, 19, 247, 10.1002/net.3230190206 · doi:10.1002/net.3230190206
  49. 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
  50. 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
  51. 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
  52. 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
  53. 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
  54. 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

See all 311

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.