{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:08:52Z","timestamp":1770062932958,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T00:00:00Z","timestamp":1730419200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T00:00:00Z","timestamp":1730419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J. Comput. Sci. Technol."],"published-print":{"date-parts":[[2024,11]]},"DOI":"10.1007\/s11390-024-2850-0","type":"journal-article","created":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:19:41Z","timestamp":1737004781000},"page":"1328-1340","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Heuristic Search with Cut Point Based Strategy for Critical Node Problem"],"prefix":"10.1007","volume":"39","author":[{"given":"Zhi-Han","family":"Chen","sequence":"first","affiliation":[]},{"given":"Shao-Wei","family":"Cai","sequence":"additional","affiliation":[]},{"given":"Jian","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Shi-Ke","family":"Ge","sequence":"additional","affiliation":[]},{"given":"Chan-Juan","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Jin-Kun","family":"Lin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,16]]},"reference":[{"issue":"3","key":"2850_CR1","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1109\/TNET.2012.2215882","volume":"21","author":"Y Shen","year":"2013","unstructured":"Shen Y, Nguyen N P, Xuan Y, Thai M T. On the discovery of critical links and nodes for assessing network vulnerability. IEEE\/ACM Trans. Networking, 2013, 21(3): 963\u2013973. DOI: https:\/\/doi.org\/10.1109\/TNET.2012.2215882.","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"2850_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1142\/9789812771667_0007","volume-title":"Clustering Challenges in Biological Networks","author":"V Boginski","year":"2009","unstructured":"Boginski V, Commander C W. Identifying critical nodes in protein-protein interaction networks. In Clustering Challenges in Biological Networks, Butenko S, Chaovalitwongse W A, Pardalos P M (eds.), World Scientific, 2009, pp.153\u2013167. DOI: https:\/\/doi.org\/10.1142\/9789812771667_0007."},{"key":"2850_CR3","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-1-4614-2107-8_10","volume-title":"Data Mining for Biomarker Discovery","author":"V Tomaino","year":"2012","unstructured":"Tomaino V, Arulselvan A, Veltri P, Pardalos P M. Studying connectivity properties in human protein\u2013protein interaction network in cancer pathway. In Data Mining for Biomarker Discovery, Pardalos P M, Xanthopoulos P, Zervakis M (eds.), Springer-Verlag, 2012, pp.187\u2013197. DOI: https:\/\/doi.org\/10.1007\/978-1-4614-2107-8_10."},{"issue":"1","key":"2850_CR4","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1109\/TSG.2012.2229398","volume":"4","author":"D T Nguyen","year":"2013","unstructured":"Nguyen D T, Shen Y, Thai M T. Detecting critical nodes in interdependent power networks for vulnerability assessment. IEEE Trans. Smart Grid, 2013, 4(1): 151\u2013159. DOI: https:\/\/doi.org\/10.1109\/TSG.2012.2229398.","journal-title":"IEEE Trans. Smart Grid"},{"issue":"6","key":"2850_CR5","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1016\/j.jcss.2006.02.003","volume":"72","author":"J Aspnes","year":"2006","unstructured":"Aspnes J, Chang K, Yampolskiy A. Inoculation strategies for victims of viruses and the sum-of-squares partition problem. Journal of Computer and System Sciences, 2006, 72(6): 1077\u20131093. DOI: https:\/\/doi.org\/10.1016\/j.jcss.2006.02.003.","journal-title":"Journal of Computer and System Sciences"},{"key":"2850_CR6","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1145\/956750.956769","volume-title":"Proc. the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug","author":"D Kempe","year":"2003","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9. Maximizing the spread of influence through a social network. In Proc. the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2003, pp.137\u2013146. DOI: https:\/\/doi.org\/10.1145\/956750.956769."},{"key":"2850_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10588-006-7084-x","volume":"12","author":"S P Borgatti","year":"2006","unstructured":"Borgatti S P. Identifying sets of key players in a social network. Computational & Mathematical Organization Theory, 2006, 12: 21\u201334. DOI: https:\/\/doi.org\/10.1007\/s10588-006-7084-x.","journal-title":"Computational & Mathematical Organization Theory"},{"issue":"7","key":"2850_CR8","doi-asserted-by":"publisher","first-page":"2193","DOI":"10.1016\/j.cor.2008.08.016","volume":"36","author":"A Arulselvan","year":"2009","unstructured":"Arulselvan A, Commander C W, Elefteriadou L, Pardalos P M. Detecting critical nodes in sparse graphs. Computers & Operations Research, 2009, 36(7): 2193\u20132200. DOI: https:\/\/doi.org\/10.1016\/j.cor.2008.08.016.","journal-title":"Computers & Operations Research"},{"issue":"2","key":"2850_CR9","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1002\/net.20464","volume":"60","author":"S Shen","year":"2012","unstructured":"Shen S, Smith J C. Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks, 2012, 60(2): 103\u2013119. DOI: https:\/\/doi.org\/10.1002\/net.20464.","journal-title":"Networks"},{"key":"2850_CR10","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.cosrev.2018.02.002","volume":"28","author":"M Lalou","year":"2018","unstructured":"Lalou M, Tahraoui M A, Kheddouci H. The critical node detection problem in networks: A survey. Computer Science Review, 2018, 28: 92\u2013117. DOI: https:\/\/doi.org\/10.1016\/j.cosrev.2018.02.002.","journal-title":"Computer Science Review"},{"issue":"3","key":"2850_CR11","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1007\/s10589-012-9458-y","volume":"53","author":"M Di Summa","year":"2012","unstructured":"Di Summa M, Grosso A, Locatelli M. Branch and cut algorithms for detecting critical nodes in undirected graphs. Computational Optimization and Applications, 2012, 53(3): 649\u2013680. DOI: https:\/\/doi.org\/10.1007\/s10589-012-9458-y.","journal-title":"Computational Optimization and Applications"},{"key":"2850_CR12","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.cor.2018.04.012","volume":"97","author":"K Pavlikov","year":"2018","unstructured":"Pavlikov K. Improved formulations for minimum connectivity network interdiction problems. Computers & Operations Research, 2018, 97: 48\u201357. DOI: https:\/\/doi.org\/10.1016\/j.cor.2018.04.012.","journal-title":"Computers & Operations Research"},{"key":"2850_CR13","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1109\/MILCOM.2011.6127492","volume-title":"Proc. the 2011 Military Communications Conference","author":"T N Dinh","year":"2011","unstructured":"Dinh T N, Thai M T. Precise structural vulnerability assessment via mathematical programming. In Proc. the 2011 Military Communications Conference, Nov. 2011, pp.1351\u20131356. DOI: https:\/\/doi.org\/10.1109\/MILCOM.2011.6127492."},{"issue":"1","key":"2850_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1002\/net.21834","volume":"73","author":"J L Walteros","year":"2019","unstructured":"Walteros J L, Veremyev A, Pardalos P M, Pasiliao E L. Detecting critical node structures on graphs: A mathematical programming approach. Networks, 2019, 73(1): 48\u201388. DOI: https:\/\/doi.org\/10.1002\/net.21834.","journal-title":"Networks"},{"key":"2850_CR15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.endm.2014.11.006","volume":"47","author":"R Aringhieri","year":"2015","unstructured":"Aringhieri R, Grosso A, Hosteins P, Scatamacchia R. VNS solutions for the critical node problem. Electronic Notes in Discrete Mathematics, 2015, 47: 37\u201344. DOI: https:\/\/doi.org\/10.1016\/j.endm.2014.11.006.","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"2850_CR16","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/j.cor.2013.09.012","volume":"43","author":"M Ventresca","year":"2014","unstructured":"Ventresca M, Aleman D. A derandomized approximation algorithm for the critical node detection problem. Computers & Operations Research, 2014, 43: 261\u2013270. DOI: https:\/\/doi.org\/10.1016\/j.cor.2013.09.012.","journal-title":"Computers & Operations Research"},{"issue":"11","key":"2850_CR17","doi-asserted-by":"publisher","first-page":"2763","DOI":"10.1016\/j.cor.2012.02.008","volume":"39","author":"M Ventresca","year":"2012","unstructured":"Ventresca M. Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Computers & Operations Research, 2012, 39(11): 2763\u20132775. DOI: https:\/\/doi.org\/10.1016\/j.cor.2012.02.008.","journal-title":"Computers & Operations Research"},{"key":"2850_CR18","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/978-3-319-12691-3_45","volume-title":"Proc. the 8th International Conference on Combinatorial Optimization and Applications","author":"M Ventresca","year":"2014","unstructured":"Ventresca M, Aleman D. A fast greedy algorithm for the critical node detection problem. In Proc. the 8th International Conference on Combinatorial Optimization and Applications, Dec. 2014, pp.603\u2013612. DOI: https:\/\/doi.org\/10.1007\/978-3-319-12691-3_45."},{"issue":"3","key":"2850_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/net.21671","volume":"67","author":"R Aringhieri","year":"2016","unstructured":"Aringhieri R, Grosso A, Hosteins P, Scatamacchia R. Local search metaheuristics for the critical node problem. Networks, 2016, 67(3): 209\u2013221. DOI: https:\/\/doi.org\/10.1002\/net.21671.","journal-title":"Networks"},{"issue":"5","key":"2850_CR20","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s10732-015-9290-5","volume":"21","author":"W Pullan","year":"2015","unstructured":"Pullan W. Heuristic identification of critical nodes in sparse real-world graphs. Journal of Heuristics, 2015, 21(5): 577\u2013598. DOI: https:\/\/doi.org\/10.1007\/s10732-015-9290-5.","journal-title":"Journal of Heuristics"},{"issue":"10","key":"2850_CR21","doi-asserted-by":"publisher","first-page":"3699","DOI":"10.1109\/TCYB.2018.2848116","volume":"49","author":"Y Zhou","year":"2019","unstructured":"Zhou Y, Hao J K, Glover F. Memetic search for identifying critical nodes in sparse graphs. IEEE Trans. Cybernetics, 2019, 49(10): 3699\u20133712. DOI: https:\/\/doi.org\/10.1109\/TCYB.2018.2848116.","journal-title":"IEEE Trans. Cybernetics"},{"issue":"1\/2","key":"2850_CR22","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/s10479-016-2110-y","volume":"238","author":"B Addis","year":"2016","unstructured":"Addis B, Aringhieri R, Grosso A, Hosteins P. Hybrid constructive heuristics for the critical node problem. Annals of Operations Research, 2016, 238(1\/2): 637\u2013649. DOI: https:\/\/doi.org\/10.1007\/s10479-016-2110-y.","journal-title":"Annals of Operations Research"},{"key":"2850_CR23","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.engappai.2016.06.010","volume":"55","author":"R Aringhieri","year":"2016","unstructured":"Aringhieri R, Grosso A, Hosteins P, Scatamacchia R. A general evolutionary framework for different classes of critical node problems. Engineering Applications of Artificial Intelligence, 2016, 55: 128\u2013145. DOI: https:\/\/doi.org\/10.1016\/j.engappai.2016.06.010.","journal-title":"Engineering Applications of Artificial Intelligence"},{"issue":"1","key":"2850_CR24","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1109\/TEVC.2020.3011959","volume":"25","author":"Y Zhou","year":"2021","unstructured":"Zhou Y, Hao J K, Fu Z H, Wang Z, Lai X. Variable population memetic search: A case study on the critical node problem. IEEE Trans. Evolutionary Computation, 2021, 25(1): 187\u2013200. DOI: https:\/\/doi.org\/10.1109\/TEVC.2020.3011959.","journal-title":"IEEE Trans. Evolutionary Computation"},{"key":"2850_CR25","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/3067695.3075993","volume-title":"Proc. the Genetic and Evolutionary Computation Conference Companion","author":"Y Zhou","year":"2017","unstructured":"Zhou Y, Hao J K. A fast heuristic algorithm for the critical node problem. In Proc. the Genetic and Evolutionary Computation Conference Companion, Jul. 2017, pp.121\u2013122. DOI: https:\/\/doi.org\/10.1145\/3067695.3075993."},{"issue":"2","key":"2850_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan R. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1972, 1(2): 146\u2013160. DOI: https:\/\/doi.org\/10.1137\/0201010.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"2850_CR27","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.ejor.2009.07.016","volume":"203","author":"Z L\u00fc","year":"2010","unstructured":"L\u00fc Z, Hao J K. A memetic algorithm for graph coloring. European Journal of Operational Research, 2010, 203(1): 241\u2013250. DOI: https:\/\/doi.org\/10.1016\/j.ejor.2009.07.016.","journal-title":"European Journal of Operational Research"},{"key":"2850_CR28","doi-asserted-by":"publisher","first-page":"4292","DOI":"10.1609\/aaai.v29i1.9277","volume-title":"Proc. the 29th AAAI Conference on Artificial Intelligence","author":"R A Rossi","year":"2015","unstructured":"Rossi R A, Ahmed N K. The network data repository with interactive graph analytics and visualization. In Proc. the 29th AAAI Conference on Artificial Intelligence, Jan. 2015, pp.4292\u20134293. DOI: https:\/\/doi.org\/10.1609\/aaai.v29i1.9277."},{"key":"2850_CR29","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1145\/2567948.2577283","volume-title":"Proc. the 23rd Int. Conf. World Wide Web","author":"R A Rossi","year":"2014","unstructured":"Rossi R A, Gleich D F, Gebremedhin A H, Patwary M M A. Fast maximum clique algorithms for large graphs. In Proc. the 23rd Int. Conf. World Wide Web, Apr. 2014, pp.365\u2013366. DOI: https:\/\/doi.org\/10.1145\/2567948.2577283."},{"key":"2850_CR30","doi-asserted-by":"publisher","first-page":"517","DOI":"10.24963\/ijcai.2017\/73","volume-title":"Proc. the 26th International Joint Conference on Artificial Intelligence","author":"J Lin","year":"2017","unstructured":"Lin J, Cai S, Luo C, Su K. A reduction based method for coloring very large graphs. In Proc. the 26th International Joint Conference on Artificial Intelligence, Aug. 2017, pp.517\u2013523. DOI: https:\/\/doi.org\/10.24963\/ijcai.2017\/73."},{"key":"2850_CR31","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.24963\/ijcai.2020\/204","volume-title":"Proc. the 29th International Joint Conference on Artificial Intelligence","author":"S Cai","year":"2020","unstructured":"Cai S, Hou W, Wang Y, Luo C, Lin Q. Two-goal local search and inference rules for minimum dominating set. In Proc. the 29th International Joint Conference on Artificial Intelligence, Jul. 2020, pp.1467\u20131473. DOI: https:\/\/doi.org\/10.24963\/ijcai.2020\/204."},{"key":"2850_CR32","volume-title":"Practical Nonparametric Statistics","author":"W J Conover","year":"1999","unstructured":"Conover W J. Practical Nonparametric Statistics (3rd edition). John Wiley & Sons, 1999.","edition":"3rd edition"},{"key":"2850_CR33","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1145\/3540250.3549155","volume-title":"Proc. the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering","author":"C Luo","year":"2022","unstructured":"Luo C, Zhao Q, Cai S, Zhang H, Hu C. SamplingCA: Effective and efficient sampling-based pairwise testing for highly configurable software systems. In Proc. the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Nov. 2022, pp.1185\u20131197. DOI: https:\/\/doi.org\/10.1145\/3540250.3549155."}],"container-title":["Journal of Computer Science and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11390-024-2850-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11390-024-2850-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11390-024-2850-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:19:45Z","timestamp":1737004785000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11390-024-2850-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["2850"],"URL":"https:\/\/doi.org\/10.1007\/s11390-024-2850-0","relation":{},"ISSN":["1000-9000","1860-4749"],"issn-type":[{"value":"1000-9000","type":"print"},{"value":"1860-4749","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11]]},"assertion":[{"value":"21 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Conflict of Interest The authors declare that they have no conflict of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics"}}]}}