{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T20:08:50Z","timestamp":1767211730628,"version":"3.44.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T00:00:00Z","timestamp":1753315200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T00:00:00Z","timestamp":1753315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2022YFB2403400)."],"award-info":[{"award-number":["2022YFB2403400)."]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s10589-025-00698-5","type":"journal-article","created":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T10:35:34Z","timestamp":1753353334000},"page":"215-263","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Preprocessing and valid inequalities for exact detection of critical nodes via integer programming"],"prefix":"10.1007","volume":"92","author":[{"given":"Sheng-Jie","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3316-8331","authenticated-orcid":false,"given":"Liang","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guang-Ming","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu-Hong","family":"Dai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,24]]},"reference":[{"issue":"1","key":"698_CR1","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0960-0779(03)00429-6","volume":"20","author":"V Latora","year":"2004","unstructured":"Latora, V., Marchiori, M.: How the science of complex networks can help developing strategies against terrorism. Chaos Solitons Fractals 20(1), 69\u201375 (2004)","journal-title":"Chaos Solitons Fractals"},{"issue":"7","key":"698_CR2","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/j.tra.2005.11.003","volume":"40","author":"E Jenelius","year":"2006","unstructured":"Jenelius, E., Petersen, T., Mattsson, L.-G.: Importance and exposure in road network vulnerability analysis. Transp. Res. Part A Policy Pract. 40(7), 537\u2013560 (2006)","journal-title":"Transp. Res. Part A Policy Pract."},{"key":"698_CR3","doi-asserted-by":"publisher","first-page":"126235","DOI":"10.1016\/j.physa.2021.126235","volume":"581","author":"S Pan","year":"2021","unstructured":"Pan, S., Yan, H., He, J., He, Z.: Vulnerability and resilience of transportation systems: A recent literature review. Phys. A 581, 126235 (2021)","journal-title":"Phys. A"},{"key":"698_CR4","doi-asserted-by":"crossref","unstructured":"He, J., Liang, H., Yuan, H.: Controlling infection by blocking nodes and links simultaneously. In: International Workshop on Internet and Network Economics, pp. 206\u2013217 (2011)","DOI":"10.1007\/978-3-642-25510-6_18"},{"issue":"1","key":"698_CR5","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1109\/TSG.2012.2229398","volume":"4","author":"DT 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 4(1), 151\u2013159 (2013)","journal-title":"IEEE Trans. Smart Grid"},{"key":"698_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.ijcip.2017.11.004","volume":"20","author":"L Faramondi","year":"2018","unstructured":"Faramondi, L., Setola, R., Panzieri, S., Pascucci, F., Oliva, G.: Finding critical nodes in infrastructure networks. Int. J. Crit. Infrastruct. Prot. 20, 3\u201315 (2018)","journal-title":"Int. J. Crit. Infrastruct. Prot."},{"key":"698_CR7","doi-asserted-by":"crossref","unstructured":"Dinh, T.N., Thai, M.T.: Precise structural vulnerability assessment via mathematical programming. In: Military Communications Conference, pp. 1351\u20131356 (2011)","DOI":"10.1109\/MILCOM.2011.6127492"},{"key":"698_CR8","doi-asserted-by":"crossref","unstructured":"Boginski, V., Commander, C.W.: Identifying critical nodes in protein-protein interaction networks. In: Clustering Challenges in Biological Networks, pp. 153\u2013167 (2009)","DOI":"10.1142\/9789812771667_0007"},{"key":"698_CR9","doi-asserted-by":"crossref","unstructured":"Tomaino, V., Arulselvan, A., Veltri, P., Pardalos, P.M.: Studying connectivity properties in human protein-protein interaction network in cancer pathway. In: Data Mining for Biomarker Discovery, pp. 187\u2013197 (2012)","DOI":"10.1007\/978-1-4614-2107-8_10"},{"issue":"7","key":"698_CR10","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. Comput. Operations Res. 36(7), 2193\u20132200 (2009)","journal-title":"Comput. Operations Res."},{"issue":"16\u201317","key":"698_CR11","doi-asserted-by":"publisher","first-page":"2349","DOI":"10.1016\/j.dam.2013.03.021","volume":"161","author":"B Addis","year":"2013","unstructured":"Addis, B., Di Summa, M., Grosso, A.: Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth. Discret. Appl. Math. 161(16\u201317), 2349\u20132360 (2013)","journal-title":"Discret. Appl. Math."},{"key":"698_CR12","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. Eng. Appl. Artif. Intell. 55, 128\u2013145 (2016)","journal-title":"Eng. Appl. Artif. Intell."},{"key":"698_CR13","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. J. Heuristics 21, 577\u2013598 (2015)","journal-title":"J. Heuristics"},{"issue":"3","key":"698_CR14","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.disopt.2012.07.001","volume":"9","author":"S Shen","year":"2012","unstructured":"Shen, S., Smith, J.C., Goli, R.: Exact interdiction models and algorithms for disconnecting networks via node deletions. Discret. Optim. 9(3), 172\u2013188 (2012)","journal-title":"Discret. Optim."},{"issue":"3","key":"698_CR15","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/net.21622","volume":"66","author":"A Veremyev","year":"2015","unstructured":"Veremyev, A., Prokopyev, O.A., Pasiliao, E.L.: Critical nodes for distance-based connectivity and related problems in graphs. Networks 66(3), 170\u2013195 (2015)","journal-title":"Networks"},{"key":"698_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s10878-014-9730-4","volume":"28","author":"A Veremyev","year":"2014","unstructured":"Veremyev, A., Prokopyev, O.A., Pasiliao, E.L.: An integer programming framework for critical elements detection in graphs. J. Comb. Optim. 28, 233\u2013273 (2014)","journal-title":"J. Comb. Optim."},{"issue":"11","key":"698_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. Comput. Operations Res. 39(11), 2763\u20132775 (2012)","journal-title":"Comput. Operations Res."},{"key":"698_CR18","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. Comput. Operations Res. 43, 261\u2013270 (2014)","journal-title":"Comput. Operations Res."},{"issue":"1","key":"698_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40649-015-0010-y","volume":"2","author":"M Ventresca","year":"2015","unstructured":"Ventresca, M., Aleman, D.: Efficiently identifying critical nodes in large complex networks. Comput. Soc. Netw. 2(1), 1\u201316 (2015)","journal-title":"Comput. Soc. Netw."},{"key":"698_CR20","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. Ann. Oper. Res. 238, 637\u2013649 (2016)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"698_CR21","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1287\/ijoc.2022.0130","volume":"36","author":"Y Zhou","year":"2024","unstructured":"Zhou, Y., Li, J., Hao, J.-K., Glover, F.: Detecting critical nodes in sparse graphs via \u201creduce-solve-combine\u2019\u2019 memetic search. INFORMS J. Comput. 36(1), 39\u201360 (2024)","journal-title":"INFORMS J. Comput."},{"key":"698_CR22","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. Comput. Sci. Rev. 28, 92\u2013117 (2018)","journal-title":"Comput. Sci. Rev."},{"issue":"17","key":"698_CR23","doi-asserted-by":"publisher","first-page":"19770","DOI":"10.1007\/s11227-023-05429-3","volume":"79","author":"A Megzari","year":"2023","unstructured":"Megzari, A., Pravija Raj, P., Osamy, W., Khedr, A.M.: Applications, challenges, and solutions to single- and multi-objective critical node detection problems: A survey. J. Supercomput. 79(17), 19770\u201319808 (2023)","journal-title":"J. Supercomput."},{"key":"698_CR24","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. Comput. Optim. Appl. 53, 649\u2013680 (2012)","journal-title":"Comput. Optim. Appl."},{"key":"698_CR25","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. Comput. Operations Res. 97, 48\u201357 (2018)","journal-title":"Comput. Operations Res."},{"key":"698_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11067-018-9407-0","volume":"19","author":"G Karakose","year":"2019","unstructured":"Karakose, G., McGarvey, R.G.: Optimal detection of critical nodes: Improvements to model structure and performance. Netw. Spat. Econ. 19, 1\u201326 (2019)","journal-title":"Netw. Spat. Econ."},{"key":"698_CR27","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1007\/s11590-013-0666-x","volume":"8","author":"A Veremyev","year":"2014","unstructured":"Veremyev, A., Boginski, V., Pasiliao, E.L.: Exact identification of critical nodes in sparse networks via new compact formulations. Optim. Lett. 8, 1245\u20131259 (2014)","journal-title":"Optim. Lett."},{"issue":"1","key":"698_CR28","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1287\/ijoc.2015.0671","volume":"28","author":"J Naoum-Sawaya","year":"2016","unstructured":"Naoum-Sawaya, J., Buchheim, C.: Robust critical node selection by Benders decomposition. INFORMS J. Comput. 28(1), 162\u2013174 (2016)","journal-title":"INFORMS J. Comput."},{"key":"698_CR29","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1016\/j.cie.2017.12.008","volume":"115","author":"G Karakose","year":"2018","unstructured":"Karakose, G., McGarvey, R.G.: Node-securing connectivity-based model to reduce infection spread in contaminated networks. Comput. Ind. Eng. 115, 512\u2013519 (2018)","journal-title":"Comput. Ind. Eng."},{"issue":"3","key":"698_CR30","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1002\/net.21948","volume":"76","author":"P Hosteins","year":"2020","unstructured":"Hosteins, P., Scatamacchia, R.: The stochastic critical node problem over trees. Networks 76(3), 381\u2013401 (2020)","journal-title":"Networks"},{"issue":"3","key":"698_CR31","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1016\/S0377-2217(03)00135-8","volume":"156","author":"Y-S Myung","year":"2004","unstructured":"Myung, Y.-S., Kim, H.-j: A cutting plane algorithm for computing $$k$$-edge survivability of a network. Eur. J. Oper. Res. 156(3), 579\u2013589 (2004)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"698_CR32","doi-asserted-by":"publisher","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen kurventheorie. Fundam. Math. 10(1), 96\u2013115 (1927)","journal-title":"Fundam. Math."},{"key":"698_CR33","volume-title":"The Algorithm Design Manual","author":"SS Skiena","year":"1998","unstructured":"Skiena, S.S.: The Algorithm Design Manual, vol. 2. Springer, London (1998)"},{"key":"698_CR34","first-page":"225","volume":"38","author":"G Dantzig","year":"2003","unstructured":"Dantzig, G., Fulkerson, D.R.: On the max flow min cut theorem of networks. Linear Inequal. Relat. Syst. 38, 225\u2013231 (2003)","journal-title":"Linear Inequal. Relat. Syst."},{"key":"698_CR35","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2022","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2022)"},{"key":"698_CR36","doi-asserted-by":"crossref","unstructured":"Balas, E.: Projection and lifting in combinatorial optimization. In: Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions, pp. 26\u201356 (2001)","DOI":"10.1007\/3-540-45586-8_2"},{"key":"698_CR37","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"9","key":"698_CR38","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: Finding all cliques of an undirected graph. Commun. ACM 16(9), 575\u2013577 (1973)","journal-title":"Commun. ACM"},{"key":"698_CR39","unstructured":"Baum, D.: Finding all maximal cliques of a family of induced subgraphs. Zuse Institute Berlin (2003)"},{"issue":"1\u20133","key":"698_CR40","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1016\/j.tcs.2008.05.010","volume":"407","author":"F Cazals","year":"2008","unstructured":"Cazals, F., Karande, C.: A note on the problem of reporting maximal cliques. Theoret. Comput. Sci. 407(1\u20133), 564\u2013568 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"698_CR41","unstructured":"IBM: IBM ILOG CPLEX Optimization Studio 20.1.0. https:\/\/www.ibm.com\/analytics\/cplex-optimizer"},{"issue":"1","key":"698_CR42","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5(1), 17\u201360 (1960)","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"issue":"5439","key":"698_CR43","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A-L Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"issue":"6684","key":"698_CR44","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440\u2013442 (1998)","journal-title":"Nature"},{"key":"698_CR45","doi-asserted-by":"crossref","unstructured":"Hagberg, A., Schult, D., Swart, P.: Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th Python in Science Conference, pp. 11\u201315 (2008)","DOI":"10.25080\/TCWV9851"},{"key":"698_CR46","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence, pp. 4292\u20134293 (2015)","DOI":"10.1609\/aaai.v29i1.9277"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00698-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-025-00698-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00698-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T21:33:46Z","timestamp":1757280826000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-025-00698-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,24]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["698"],"URL":"https:\/\/doi.org\/10.1007\/s10589-025-00698-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2025,7,24]]},"assertion":[{"value":"28 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}