{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T21:40:05Z","timestamp":1771018805963,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T00:00:00Z","timestamp":1563580800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T00:00:00Z","timestamp":1563580800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s10479-019-03315-x","type":"journal-article","created":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T11:02:21Z","timestamp":1563620541000},"page":"345-376","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Minimum cost edge blocker clique problem"],"prefix":"10.1007","volume":"294","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9009-9363","authenticated-orcid":false,"given":"Foad","family":"Mahdavi Pajouh","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,20]]},"reference":[{"key":"3315_CR1","series-title":"DIMACS series on discrete mathematics and theoretical computer science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1090\/dimacs\/050\/06","volume-title":"External memory algorithms and visualization","author":"J Abello","year":"1999","unstructured":"Abello, J., Pardalos, P., & Resende, M. (1999). On maximum clique problems in very large graphs. In J. Abello & J. Vitter (Eds.), External memory algorithms and visualization (Vol. 50, pp. 119\u2013130)., DIMACS series on discrete mathematics and theoretical computer science Providence: American Mathematical Society."},{"issue":"4","key":"3315_CR2","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1002\/net.21732","volume":"69","author":"M Afshari Rad","year":"2017","unstructured":"Afshari Rad, M., & Kakhki, H. T. (2017). Two extended formulations for cardinality maximum flow network interdiction problem. Networks, 69(4), 367\u2013377.","journal-title":"Networks"},{"issue":"1","key":"3315_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.orl.2009.09.013","volume":"38","author":"DS Altner","year":"2010","unstructured":"Altner, D. S., Ergun, O., & Uhan, N. A. (2010). The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability. Operations Research Letters, 38(1), 33\u201338.","journal-title":"Operations Research Letters"},{"issue":"7","key":"3315_CR4","doi-asserted-by":"crossref","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. (2009). Detecting critical nodes in sparse graphs. Computers & Operations Research, 36(7), 2193\u20132200.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"3315_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-4-2","volume":"4","author":"GD Bader","year":"2003","unstructured":"Bader, G. D., & Hogue, C. W. V. (2003). An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4(1), 1\u201327. https:\/\/doi.org\/10.1186\/1471-2105-4-2.","journal-title":"BMC Bioinformatics"},{"key":"3315_CR6","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1002\/9780470253489.ch6","volume-title":"Analysis of biological networks","author":"B Balasundaram","year":"2008","unstructured":"Balasundaram, B., & Butenko, S. (2008). Network clustering. In B. H. Junker & F. Schreiber (Eds.), Analysis of biological networks (pp. 113\u2013138). New York: Wiley."},{"key":"3315_CR7","unstructured":"Bar-Noy, A., Khuller, S., & Schieber, B. (1995). The complexity of finding most vital arcs and nodes. Tech. Rep. CS-TR-3539, Department of Computer Science, University of Maryland."},{"issue":"17","key":"3315_CR8","doi-asserted-by":"crossref","first-page":"1933","DOI":"10.1016\/j.dam.2011.06.023","volume":"159","author":"C Bazgan","year":"2011","unstructured":"Bazgan, C., Toubaline, S., & Tuza, Z. (2011). The most vital nodes with respect to independent set and vertex cover. Discrete Applied Mathematics, 159(17), 1933\u20131946.","journal-title":"Discrete Applied Mathematics"},{"key":"3315_CR9","doi-asserted-by":"crossref","unstructured":"Bazgan, C., Toubaline, S., & Vanderpooten, D. (2010). Complexity of determining the most vital elements for the 1-median and 1-center location problems. In Proceedings of the 4th annual international conference on combinatorial optimization and applications, COCOA (Vol. 6508, pp. 237\u2013251).","DOI":"10.1007\/978-3-642-17458-2_20"},{"issue":"1","key":"3315_CR10","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/s10878-011-9449-4","volume":"26","author":"C Bazgan","year":"2013","unstructured":"Bazgan, C., Toubaline, S., & Vanderpooten, D. (2013). Critical edges\/nodes for the minimum spanning tree problem: Complexity and approximation. Journal of Combinatorial Optimization, 26(1), 178\u2013189.","journal-title":"Journal of Combinatorial Optimization"},{"key":"3315_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2005.05.026","volume":"173","author":"S Butenko","year":"2006","unstructured":"Butenko, S., & Wilhelm, W. (2006). Clique-detection models in computational biochemistry and genomics. European Journal of Operational Research, 173, 1\u201317.","journal-title":"European Journal of Operational Research"},{"issue":"12","key":"3315_CR12","doi-asserted-by":"crossref","first-page":"1766","DOI":"10.1016\/j.cor.2011.02.016","volume":"38","author":"M Di Summa","year":"2011","unstructured":"Di Summa, M., Grosso, A., & Locatelli, M. (2011). Complexity of the critical node problem over trees. Computers & Operations Research, 38(12), 1766\u20131774.","journal-title":"Computers & Operations Research"},{"issue":"3","key":"3315_CR13","doi-asserted-by":"crossref","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. (2012). Branch and cut algorithms for detecting critical nodes in undirected graphs. Computational Optimization and Applications, 53(3), 649\u2013680.","journal-title":"Computational Optimization and Applications"},{"issue":"1","key":"3315_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10878-014-9742-0","volume":"28","author":"TN Dinh","year":"2014","unstructured":"Dinh, T. N., Thai, M. T., & Nguyen, H. T. (2014). Bound and exact methods for assessing link vulnerability in complex networks. Journal of Combinatorial Optimization, 28(1), 3\u201324.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2","key":"3315_CR15","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1109\/TNET.2011.2170849","volume":"20","author":"TN Dinh","year":"2012","unstructured":"Dinh, T. N., Xuan, Y., Thai, M. T., Pardalos, P. M., & Znati, T. (2012). On new approaches of assessing network vulnerability: Hardness and approximation. IEEE\/ACM Transactions on Networking, 20(2), 609\u2013619.","journal-title":"IEEE\/ACM Transactions on Networking"},{"issue":"6","key":"3315_CR16","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1287\/opre.2017.1650","volume":"65","author":"M Fischetti","year":"2017","unstructured":"Fischetti, M., Ljubi\u0107, I., Monaci, M., & Sinnl, M. (2017). A new general-purpose algorithm for mixed-integer bilevel linear programs. Operations Research, 65(6), 1615\u20131637. https:\/\/doi.org\/10.1287\/opre.2017.1650.","journal-title":"Operations Research"},{"key":"3315_CR17","unstructured":"Frederickson, G. N., & Solis-Oba, R. (1996). Increasing the weight of minimum spanning trees. In Proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 539\u2013546)."},{"issue":"1","key":"3315_CR18","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1002\/nav.3800180103","volume":"18","author":"PM Ghare","year":"1971","unstructured":"Ghare, P. M., Montgomery, D. C., & Turner, W. C. (1971). Optimal interdiction policy for a flow network. Naval Research Logistics Quarterly, 18(1), 37\u201345.","journal-title":"Naval Research Logistics Quarterly"},{"key":"3315_CR19","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1186\/1471-2458-8-61","volume":"8","author":"LM Glass","year":"2008","unstructured":"Glass, L. M., & Glass, R. J. (2008). Social contact networks for the spread of pandemic influenza in children and teenagers. BMC Public Health, 8, 61.","journal-title":"BMC Public Health"},{"issue":"2","key":"3315_CR20","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1002\/net.10039","volume":"40","author":"E Israeli","year":"2002","unstructured":"Israeli, E., & Wood, R. K. (2002). Shortest-path network interdiction. Networks, 40(2), 97\u2013111.","journal-title":"Networks"},{"key":"3315_CR21","doi-asserted-by":"publisher","unstructured":"Karp, R. (1972). Reducibility among combinatorial problems. In R. Miller, J. Thatcher, & J. Bohlinger (Eds.), Complexity of computer computations. The IBM research symposia series (pp. 85\u2013103). New York: Springer. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2","key":"3315_CR22","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/s00224-007-9025-6","volume":"43","author":"L Khachiyan","year":"2008","unstructured":"Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Rudolf, G., et al. (2008). On short paths interdiction problems: Total and node-wise limited interdiction. Theory of Computing Systems, 43(2), 204\u2013233.","journal-title":"Theory of Computing Systems"},{"key":"3315_CR23","volume-title":"The art of computer programming: Sorting and searching","author":"D Knuth","year":"1998","unstructured":"Knuth, D. (1998). The art of computer programming: Sorting and searching (2nd ed., Vol. 3). Redwood City: Addison Wesley Longman Publishing Co., Inc.","edition":"2"},{"issue":"1","key":"3315_CR24","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0020-0190(93)90247-7","volume":"45","author":"KC Lin","year":"1993","unstructured":"Lin, K. C., & Chern, M. S. (1993). The most vital edges in the minimum spanning tree problem. Information Processing Letters, 45(1), 25\u201331.","journal-title":"Information Processing Letters"},{"issue":"1","key":"3315_CR25","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1002\/net.21556","volume":"64","author":"F Mahdavi Pajouh","year":"2014","unstructured":"Mahdavi Pajouh, F., Boginski, V., & Pasiliao, E. L. (2014). Minimum vertex blocker clique problem. Networks, 64(1), 48\u201364. https:\/\/doi.org\/10.1002\/net.21556.","journal-title":"Networks"},{"issue":"1","key":"3315_CR26","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.ejor.2015.05.037","volume":"247","author":"F Mahdavi Pajouh","year":"2015","unstructured":"Mahdavi Pajouh, F., Walteros, J. L., Boginski, V., & Pasiliao, E. L. (2015). Minimum edge blocker dominating set problem. European Journal of Operational Research, 247(1), 16\u201326.","journal-title":"European Journal of Operational Research"},{"key":"3315_CR27","unstructured":"Miller, R. E., & Muller, D. E. (1960). A problem of maximum consistent subsets. Tech. Rep. RC\u2013240, IBM Research Report."},{"issue":"1","key":"3315_CR28","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J. W., & Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1), 23\u201328.","journal-title":"Israel Journal of Mathematics"},{"issue":"4","key":"3315_CR29","first-page":"424","volume":"8","author":"PRJ \u00d6sterg\u00e5rd","year":"2001","unstructured":"\u00d6sterg\u00e5rd, P. R. J. (2001). A new algorithm for the maximum-weight clique problem. Nordic Journal of Computing, 8(4), 424\u2013436.","journal-title":"Nordic Journal of Computing"},{"issue":"11","key":"3315_CR30","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.disc.2009.08.009","volume":"310","author":"B Ries","year":"2010","unstructured":"Ries, B., Bentz, C., Picouleau, C., de Werra, D., Costa, M., & Zenklusen, R. (2010). Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid. Discrete Mathematics, 310(11), 132\u2013146.","journal-title":"Discrete Mathematics"},{"key":"3315_CR31","unstructured":"Ryan, A. R., & Nesreen, K. A. (2015). The network data repository with interactive graph analytics and visualization. In Proceedings of the twenty-ninth AAAI conference on artificial intelligence. http:\/\/networkrepository.com."},{"key":"3315_CR32","volume-title":"Social network analysis: A handbook","author":"J Scott","year":"2000","unstructured":"Scott, J. (2000). Social network analysis: A handbook (2nd ed.). London: Sage Publications.","edition":"2"},{"issue":"3","key":"3315_CR33","doi-asserted-by":"crossref","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. (2013). On the discovery of critical links and nodes for assessing network vulnerability. IEEE\/ACM Transactions on Networking (TON), 21(3), 963\u2013973.","journal-title":"IEEE\/ACM Transactions on Networking (TON)"},{"issue":"21","key":"3315_CR34","doi-asserted-by":"crossref","first-page":"12,123","DOI":"10.1073\/pnas.2032324100","volume":"100","author":"V Spirin","year":"2003","unstructured":"Spirin, V., & Mirny, L. A. (2003). Protein complexes and functional modules in molecular networks. Proceedings of the National Academy of Sciences, 100(21), 12,123\u201312,128.","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"2","key":"3315_CR35","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10898-015-0274-7","volume":"66","author":"Y Tang","year":"2016","unstructured":"Tang, Y., Richard, J. P. P., & Smith, J. C. (2016). A class of algorithms for mixed-integer bilevel min\u2013max optimization. Journal of Global Optimization, 66(2), 225\u2013262.","journal-title":"Journal of Global Optimization"},{"issue":"4","key":"3315_CR36","doi-asserted-by":"crossref","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. (2014a). Exact identification of critical nodes in sparse networks via new compact formulations. Optimization Letters, 8(4), 1245\u20131259.","journal-title":"Optimization Letters"},{"issue":"1","key":"3315_CR37","doi-asserted-by":"crossref","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. (2014b). An integer programming framework for critical elements detection in graphs. Journal of Combinatorial Optimization, 28(1), 233\u2013273.","journal-title":"Journal of Combinatorial Optimization"},{"key":"3315_CR38","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511815478","volume-title":"Social network analysis","author":"S Wasserman","year":"1994","unstructured":"Wasserman, S., & Faust, K. (1994). Social network analysis. New York: Cambridge University Press."},{"issue":"6","key":"3315_CR39","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1287\/opre.12.6.934","volume":"12","author":"R Wollmer","year":"1964","unstructured":"Wollmer, R. (1964). Removing arcs from a network. Operations Research, 12(6), 934\u2013940.","journal-title":"Operations Research"},{"key":"3315_CR40","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.is.2016.12.002","volume":"65","author":"P Wong","year":"2017","unstructured":"Wong, P., Sun, C., Lo, E., Yiu, M. L., Wu, X., Zhao, Z., et al. (2017). Finding $$k$$ most influential edges on flow graphs. Information Systems, 65, 93\u2013105.","journal-title":"Information Systems"},{"issue":"2","key":"3315_CR41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0895-7177(93)90236-R","volume":"17","author":"RK Wood","year":"1993","unstructured":"Wood, R. K. (1993). Deterministic network interdiction. Mathematical and Computer Modeling, 17(2), 1\u201318.","journal-title":"Mathematical and Computer Modeling"},{"key":"3315_CR42","doi-asserted-by":"publisher","unstructured":"Wu, Q., & Hao, J. K. (2015). A review on algorithms for maximum clique problems. European Journal of Operational Research, 242(3), 693\u2013709. https:\/\/doi.org\/10.1016\/j.ejor.2014.09.064, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0377221714008030.","DOI":"10.1016\/j.ejor.2014.09.064"},{"key":"3315_CR43","doi-asserted-by":"publisher","unstructured":"Yezerska, O., Pajouh, F. M., & Butenko, S. (2017b). On biconnected and fragile subgraphs of low diameter. European Journal of Operational Research, 263(2), 390\u2013400. https:\/\/doi.org\/10.1016\/j.ejor.2017.05.020, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0377221717304484.","DOI":"10.1016\/j.ejor.2017.05.020"},{"key":"3315_CR44","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-017-2665-2","author":"O Yezerska","year":"2017","unstructured":"Yezerska, O., Mahdavi Pajouh, F., Veremyev, A., & Butenko, S. (2017a). Exact algorithms for the minimum s-club partitioning problem. Annals of Operations Research,. https:\/\/doi.org\/10.1007\/s10479-017-2665-2.","journal-title":"Annals of Operations Research"},{"issue":"13","key":"3315_CR45","doi-asserted-by":"crossref","first-page":"1441","DOI":"10.1016\/j.dam.2010.04.008","volume":"158","author":"R Zenklusen","year":"2010","unstructured":"Zenklusen, R. (2010). Network flow interdiction on planar graphs. Discrete Applied Mathematics, 158(13), 1441\u20131455.","journal-title":"Discrete Applied Mathematics"},{"issue":"13","key":"3315_CR46","doi-asserted-by":"crossref","first-page":"4306","DOI":"10.1016\/j.disc.2009.01.006","volume":"309","author":"R Zenklusen","year":"2009","unstructured":"Zenklusen, R., Ries, B., Picouleau, C., de Werra, D., Costa, M., & Bentz, C. (2009). Blockers and transversals. Discrete Mathematics, 309(13), 4306\u20134314.","journal-title":"Discrete Mathematics"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03315-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-019-03315-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03315-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T15:33:38Z","timestamp":1605281618000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-019-03315-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,20]]},"references-count":46,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["3315"],"URL":"https:\/\/doi.org\/10.1007\/s10479-019-03315-x","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,20]]},"assertion":[{"value":"20 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}