{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T15:24:25Z","timestamp":1774279465503,"version":"3.50.1"},"reference-count":84,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"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":["Math. Prog. Comp."],"published-print":{"date-parts":[[2023,3]]},"DOI":"10.1007\/s12532-022-00228-y","type":"journal-article","created":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T19:05:59Z","timestamp":1667847959000},"page":"103-151","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations"],"prefix":"10.1007","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7260-7755","authenticated-orcid":false,"given":"Demetrios V.","family":"Papazaharias","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8258-7532","authenticated-orcid":false,"given":"Jose L.","family":"Walteros","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,7]]},"reference":[{"issue":"2","key":"228_CR1","doi-asserted-by":"publisher","first-page":"2068","DOI":"10.1109\/TSG.2017.2788040","volume":"10","author":"A Abusorrah","year":"2017","unstructured":"Abusorrah, A., Alabdulwahab, A., Li, Z., Shahidehpour, M.: Minimax-regret robust defensive strategy against false data injection attacks. IEEE Trans. Smart Grid 10(2), 2068\u20132079 (2017)","journal-title":"IEEE Trans. Smart Grid"},{"key":"228_CR2","unstructured":"Achterberg, T.: Constraint integer programming. PhD thesis, Technische Universit\u00e4t Berlin (2007)"},{"issue":"1","key":"228_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(93)90137-D","volume":"45","author":"E Agasi","year":"1993","unstructured":"Agasi, E., Becker, R.I., Perl, Y.: A shifting algorithm for constrained min\u2013max partition on trees. Discrete Appl. Math. 45(1), 1\u201328 (1993)","journal-title":"Discrete Appl. Math."},{"key":"228_CR4","doi-asserted-by":"publisher","DOI":"10.21236\/ADA594171","volume-title":"Network Flows","author":"RK Ahuja","year":"1988","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, Englewood Cliffs (1988)"},{"issue":"1","key":"228_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., Barab\u00e1si, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47 (2002)","journal-title":"Rev. Mod. Phys."},{"issue":"3","key":"228_CR6","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/net.21944","volume":"76","author":"Z Ales","year":"2020","unstructured":"Ales, Z., Knippel, A.: The $$k$$-partitioning problem: formulations and branch-and-cut. Networks 76(3), 323\u2013349 (2020)","journal-title":"Networks"},{"issue":"6","key":"228_CR7","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s00224-006-1350-7","volume":"39","author":"K Andreev","year":"2006","unstructured":"Andreev, K., Racke, H.: Balanced graph partitioning. Theory Comput. Syst. 39(6), 929\u2013939 (2006)","journal-title":"Theory Comput. Syst."},{"key":"228_CR8","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.dam.2017.12.035","volume":"253","author":"R Aringhieri","year":"2019","unstructured":"Aringhieri, R., Grosso, A., Hosteins, P., Scatamacchia, R.: Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem. Discrete Appl. Math. 253, 103\u2013121 (2019)","journal-title":"Discrete Appl. Math."},{"issue":"7","key":"228_CR9","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. Oper. Res. 36(7), 2193\u20132200 (2009)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"228_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02614506","volume":"78","author":"E Balas","year":"1996","unstructured":"Balas, E., Fischetti, M.: On the monotonization of polyhedra. Math. Program. 78(1), 59\u201384 (1996)","journal-title":"Math. Program."},{"issue":"\u20133","key":"228_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01582278","volume":"43","author":"E Balas","year":"1989","unstructured":"Balas, E., Ng, S.M.: On the set covering polytope: I. All the facets with coefficients in 0, 1, 2. Math. Program. 43(3), 57\u201369 (1989)","journal-title":"Math. Program."},{"key":"228_CR12","volume-title":"Linear Programming and Network Flows","author":"MS Bazaraa","year":"2008","unstructured":"Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. Wiley, Hoboken (2008)"},{"issue":"3","key":"228_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1051\/ita\/1982160302551","volume":"16","author":"P Bertolazzi","year":"1982","unstructured":"Bertolazzi, P., Lucertini, M., Spaccamela, A.M.: Analysis of a class of graph partitioning problems. RAIRO. Informatique th\u00e9orique 16(3), 255\u2013261 (1982)","journal-title":"RAIRO. Informatique th\u00e9orique"},{"key":"228_CR14","unstructured":"Buchin, M., Selbach, L.: A polynomial-time partitioning algorithm for weighted cactus graphs (2020). arXiv:2001.00204"},{"key":"228_CR15","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-319-49487-6_4","volume-title":"Algorithm Engineering: Selected Results and Surveys","author":"A Bulu\u00e7","year":"2016","unstructured":"Bulu\u00e7, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering: Selected Results and Surveys, pp. 117\u2013158. Springer, Berlin (2016)"},{"issue":"1","key":"228_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0167-6377(01)00106-7","volume":"30","author":"RD Carr","year":"2002","unstructured":"Carr, R.D., Lancia, G.: Compact vs. exponential-size lp relaxations. Oper. Res. Lett. 30(1), 57\u201365 (2002)","journal-title":"Oper. Res. Lett."},{"issue":"18","key":"228_CR17","doi-asserted-by":"publisher","first-page":"2283","DOI":"10.1093\/bioinformatics\/btl370","volume":"22","author":"J Chen","year":"2006","unstructured":"Chen, J., Yuan, B.: Detecting functional modules in the yeast protein\u2013protein interaction network. Bioinformatics 22(18), 2283\u20132290 (2006)","journal-title":"Bioinformatics"},{"issue":"1","key":"228_CR18","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1137\/S0895480191199415","volume":"7","author":"S Chopra","year":"1994","unstructured":"Chopra, S.: The graph partitioning polytope on series-parallel and 4-wheel free graphs. SIAM J. Discrete Math. 7(1), 16\u201331 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20133","key":"228_CR19","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF01581239","volume":"59","author":"S Chopra","year":"1993","unstructured":"Chopra, S., Rao, M.R.: The partition problem. Math. Program. 59(1\u20133), 87\u2013115 (1993)","journal-title":"Math. Program."},{"issue":"4","key":"228_CR20","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4(4), 305\u2013337 (1973)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"228_CR21","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0012-365X(90)90360-T","volume":"86","author":"V Chv\u00e1tal","year":"1990","unstructured":"Chv\u00e1tal, V., Cook, W.: The discipline number of a graph. Discrete Math. 86(1\u20133), 191\u2013198 (1990)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"228_CR22","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF01588778","volume":"49","author":"M Conforti","year":"1990","unstructured":"Conforti, M., Rao, M.R., Sassano, A.: The equipartition polytope. I: formulations, dimension and basic facets. Math. Program. 49(1\u20133), 49\u201370 (1990)","journal-title":"Math. Program."},{"issue":"1","key":"228_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10288-010-0122-z","volume":"8","author":"M Conforti","year":"2010","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR Q. J. Oper. Res. 8(1), 1\u201348 (2010)","journal-title":"4OR Q. J. Oper. Res."},{"issue":"2","key":"228_CR24","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/BF02592027","volume":"36","author":"WH Cunningham","year":"1986","unstructured":"Cunningham, W.H., Green-Krotki, J.: Dominants and submissives of matching polyhedra. Math. Program. 36(2), 228\u2013237 (1986)","journal-title":"Math. Program."},{"issue":"6","key":"228_CR25","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1016\/S0305-0548(01)00056-9","volume":"29","author":"SJ D\u2019Amico","year":"2002","unstructured":"D\u2019Amico, S.J., Wang, S.-J., Batta, R., Rump, C.M.: A simulated annealing approach to police district design. Comput. Oper. Res. 29(6), 667\u2013684 (2002)","journal-title":"Comput. Oper. Res."},{"key":"228_CR26","volume-title":"Graph Theory with Applications to Engineering and Computer Science","author":"N Deo","year":"2017","unstructured":"Deo, N.: Graph Theory with Applications to Engineering and Computer Science. Courier Dover Publications, Mineola (2017)"},{"issue":"3","key":"228_CR27","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(3), 649\u2013680 (2012)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"228_CR28","first-page":"17","volume":"5","author":"P Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P., R\u00e9nyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5(1), 17\u201360 (1960)","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"228_CR29","first-page":"109","volume":"57","author":"U Faigle","year":"1987","unstructured":"Faigle, U., Schrader, R., Suletzki, R.: A cutting plane algorithm for optimal graph partitioning. Methods Oper. Res. 57, 109\u2013116 (1987)","journal-title":"Methods Oper. Res."},{"issue":"3","key":"228_CR30","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02592198","volume":"74","author":"CE Ferreira","year":"1996","unstructured":"Ferreira, C.E., Martin, A., de Souza, C.C., Weismantel, R., Wolsey, L.A.: Formulations and valid inequalities for the node capacitated graph partitioning problem. Math. Program. 74(3), 247\u2013266 (1996)","journal-title":"Math. Program."},{"issue":"2","key":"228_CR31","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF01581107","volume":"81","author":"CE Ferreira","year":"1998","unstructured":"Ferreira, C.E., Martin, A., de Souza, C.C., Weismantel, R., Wolsey, L.A.: The node capacitated graph partitioning problem: a computational study. Math. Program. 81(2), 229\u2013256 (1998)","journal-title":"Math. Program."},{"issue":"3","key":"228_CR32","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75\u2013174 (2010)","journal-title":"Phys. Rep."},{"key":"228_CR33","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-540-25960-2_32","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Frangioni","year":"2004","unstructured":"Frangioni, A., Lodi, A., Rinaldi, G.: Optimizing over semimetric polytopes. In: Bienstock, D., Nemhauser, G. (eds.) Integer Programming and Combinatorial Optimization, pp. 431\u2013443. Springer, Berlin (2004)"},{"issue":"2\u20133","key":"228_CR34","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10107-005-0620-5","volume":"104","author":"A Frangioni","year":"2005","unstructured":"Frangioni, A., Lodi, A., Rinaldi, G.: New approaches for optimizing over the semimetric polytope. Math. Program. 104(2\u20133), 375\u2013388 (2005)","journal-title":"Math. Program."},{"issue":"260\u2013302","key":"228_CR35","first-page":"14","volume":"64","author":"RE Gomory","year":"1963","unstructured":"Gomory, R.E.: An algorithm for integer solutions to linear programs. Recent Adv. Math. Program. 64(260\u2013302), 14 (1963)","journal-title":"Recent Adv. Math. Program."},{"issue":"1\u20133","key":"228_CR36","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01589097","volume":"45","author":"M Gr\u00f6tschel","year":"1989","unstructured":"Gr\u00f6tschel, M., Wakabayashi, Y.: A cutting plane algorithm for a clustering problem. Math. Program. 45(1\u20133), 59\u201396 (1989)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"228_CR37","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF01580870","volume":"47","author":"M Gr\u00f6tschel","year":"1990","unstructured":"Gr\u00f6tschel, M., Wakabayashi, Y.: Facets of the clique partitioning polytope. Math. Program. 47(1\u20133), 367\u2013387 (1990)","journal-title":"Math. Program."},{"issue":"2","key":"228_CR38","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"1","key":"228_CR39","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s12532-020-00186-3","volume":"13","author":"C Hojny","year":"2021","unstructured":"Hojny, C., Joormann, I., L\u00fcthen, H., Schmidt, M.: Mixed-integer programming techniques for the connected max-$$k$$-cut problem. Math. Program. Comput. 13(1), 75\u2013132 (2021)","journal-title":"Math. Program. Comput."},{"key":"228_CR40","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16, 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"issue":"2","key":"228_CR41","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/net.10039","volume":"40","author":"E Israeli","year":"2002","unstructured":"Israeli, E., Wood, R.K.: Shortest-path network interdiction. Networks 40(2), 97\u2013111 (2002)","journal-title":"Networks"},{"issue":"3","key":"228_CR42","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1007\/s00453-010-9485-y","volume":"62","author":"T Ito","year":"2012","unstructured":"Ito, T., Nishizeki, T., Schr\u00f6der, M., Uno, T., Zhou, X.: Partitioning a weighted tree into subtrees with weights in a given range. Algorithmica 62(3), 823\u2013841 (2012)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"228_CR43","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01585164","volume":"62","author":"EL Johnson","year":"1993","unstructured":"Johnson, E.L., Mehrotra, A., Nemhauser, G.L.: Min-cut clustering. Math. Programm. 62(1\u20133), 133\u2013151 (1993)","journal-title":"Math. Programm."},{"key":"228_CR44","doi-asserted-by":"publisher","DOI":"10.1007\/978-90-481-9591-6","volume-title":"VLSI Physical Design: From Graph Partitioning to Timing Closure","author":"AB Kahng","year":"2011","unstructured":"Kahng, A.B., Lienig, J., Markov, I.L., Hu, J.: VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, Berlin (2011)"},{"issue":"1","key":"228_CR45","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0206012","volume":"6","author":"S Kundu","year":"1977","unstructured":"Kundu, S., Misra, J.: A linear tree partitioning algorithm. SIAM J. Comput. 6(1), 151\u2013154 (1977)","journal-title":"SIAM J. Comput."},{"issue":"24","key":"228_CR46","doi-asserted-by":"publisher","first-page":"3473","DOI":"10.1016\/j.disc.2010.08.009","volume":"310","author":"M Labb\u00e9","year":"2010","unstructured":"Labb\u00e9, M., \u00d6zsoy, F.A.: Size-constrained graph partitioning polytopes. Discrete Math. 310(24), 3473\u20133493 (2010)","journal-title":"Discrete Math."},{"key":"228_CR47","first-page":"221","volume-title":"Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift","author":"M Laurent","year":"1991","unstructured":"Laurent, M., Deza, M., Gr\u00f6tschel, M.: Complete descriptions of small multicut polytopes. In: Gritzmann, P., Sturmfels, B., Klee, V. (eds.) Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, vol. 4, pp. 221\u2013252. American Mathematical Soc., Providence (1991)"},{"issue":"4","key":"228_CR48","doi-asserted-by":"publisher","first-page":"1802","DOI":"10.1109\/TSG.2015.2508449","volume":"8","author":"X Liu","year":"2016","unstructured":"Liu, X., Li, Z., Li, Z.: Optimal protection strategy against false data injection attacks in power systems. IEEE Trans. Smart Grid 8(4), 1802\u20131810 (2016)","journal-title":"IEEE Trans. Smart Grid"},{"key":"228_CR49","unstructured":"Lozovanu, D., Zelikovsky, A.: Minimal and bounded tree problems. Tezele Congresului XVIII al Academiei Romano-Americane, Kishniev, p.\u00a025 (1993)"},{"issue":"3","key":"228_CR50","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1147\/rd.183.0217","volume":"18","author":"JA Lukes","year":"1974","unstructured":"Lukes, J.A.: Efficient algorithm for the partitioning of trees. IBM J. Res. Dev. 18(3), 217\u2013224 (1974)","journal-title":"IBM J. Res. Dev."},{"issue":"1","key":"228_CR51","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.: Minimum vertex blocker clique problem. Networks 64(1), 48\u201364 (2014)","journal-title":"Networks"},{"issue":"1","key":"228_CR52","doi-asserted-by":"publisher","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.: Minimum edge blocker dominating set problem. Eur. J. Oper. Res. 247(1), 16\u201326 (2015)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"228_CR53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-6377(98)00006-6","volume":"22","author":"A Mehrotra","year":"1998","unstructured":"Mehrotra, A., Trick, M.A.: Cliques and clustering: A combinatorial approach. Oper. Res. Lett. 22(1), 1\u201312 (1998)","journal-title":"Oper. Res. Lett."},{"key":"228_CR54","unstructured":"Mittelmann, H.: Benchmarks for optimization software (2018). http:\/\/plato.asu.edu\/bench.html. Last accessed May 2021"},{"issue":"3","key":"228_CR55","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."},{"key":"228_CR56","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)"},{"issue":"2","key":"228_CR57","doi-asserted-by":"publisher","first-page":"28003","DOI":"10.1209\/0295-5075\/103\/28003","volume":"103","author":"MEJ Newman","year":"2013","unstructured":"Newman, M.E.J.: Community detection and graph partitioning. Europhys. Lett. 103(2), 28003 (2013)","journal-title":"Europhys. Lett."},{"key":"228_CR58","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.disopt.2016.05.003","volume":"25","author":"DP Nguyen","year":"2017","unstructured":"Nguyen, D.P., Minoux, M., Nguyen, V.H., Nguyen, T.H., Sirdey, R.: Improved compact formulations for a wide class of graph partitioning problems in sparse graphs. Discrete Optim. 25, 175\u2013188 (2017)","journal-title":"Discrete Optim."},{"issue":"4","key":"228_CR59","first-page":"209","volume":"38","author":"M Oosten","year":"2001","unstructured":"Oosten, M., Rutten, J.H.G.C., Spieksma, F.C.R.: The clique partitioning problem: facets and patching facets. Netw. Int. J. 38(4), 209\u2013226 (2001)","journal-title":"Netw. Int. J."},{"issue":"1","key":"228_CR60","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1111\/j.1467-9574.2007.00350.x","volume":"61","author":"M Oosten","year":"2007","unstructured":"Oosten, M., Rutten, J.H.G.C., Spieksma, F.C.R.: Disconnecting graphs by removing vertices: a polyhedral approach. Stat. Neerl. 61(1), 35\u201360 (2007)","journal-title":"Stat. Neerl."},{"key":"228_CR61","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7114648","author":"DV Papazaharias","year":"2022","unstructured":"Papazaharias, D.V., Walteros, J.L.: Solving graph partitioning problems on sparse graphs. Implementation (2022). https:\/\/doi.org\/10.5281\/zenodo.7114648","journal-title":"Implementation"},{"key":"228_CR62","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). http:\/\/networkrepository.com","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"3","key":"228_CR63","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1287\/ijoc.2021.1136","volume":"34","author":"H Salemi","year":"2022","unstructured":"Salemi, H., Buchanan, A.: Solving the distance-based critical node problem. INFORMS J. Comput. 34(3), 1309\u20131326 (2022)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"228_CR64","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"SE Schaeffer","year":"2007","unstructured":"Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27\u201364 (2007)","journal-title":"Comput. Sci. Rev."},{"key":"228_CR65","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"issue":"2","key":"228_CR66","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 60(2), 103\u2013119 (2012)","journal-title":"Networks"},{"issue":"3","key":"228_CR67","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. Discrete Optim. 9(3), 172\u2013188 (2012)","journal-title":"Discrete Optim."},{"issue":"1","key":"228_CR68","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10479-011-0883-6","volume":"210","author":"HD Sherali","year":"2013","unstructured":"Sherali, H.D., Lunday, B.J.: On generating maximal nondominated benders cuts. Ann. Oper. Res. 210(1), 57\u201372 (2013)","journal-title":"Ann. Oper. Res."},{"issue":"8","key":"228_CR69","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888\u2013905 (2000)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"3","key":"228_CR70","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1016\/j.ejor.2019.06.024","volume":"283","author":"JC Smith","year":"2020","unstructured":"Smith, J.C., Song, Y.: A survey of network interdiction models and algorithms. Eur. J. Oper. Res. 283(3), 797\u2013811 (2020)","journal-title":"Eur. J. Oper. Res."},{"key":"228_CR71","unstructured":"S\u00f8rensen, M.M.: A polyhedral approach to graph partitioning. PhD thesis, Aarhus School of Business (1995)"},{"issue":"2","key":"228_CR72","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1023\/B:JOCO.0000031417.96218.26","volume":"8","author":"MM S\u00f8rensen","year":"2004","unstructured":"S\u00f8rensen, M.M.: $$b$$-tree facets for the simple graph partitioning polytope. J. Comb. Optim. 8(2), 151\u2013170 (2004)","journal-title":"J. Comb. Optim."},{"key":"228_CR73","unstructured":"S\u00f8rensen, M.M.: Polyhedral computations for the simple graph partitioning problem. Technical report, Aarhus School of Business, Department of Accounting, Finance and Logistics (2005)"},{"issue":"2","key":"228_CR74","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.disopt.2006.08.001","volume":"4","author":"MM S\u00f8rensen","year":"2007","unstructured":"S\u00f8rensen, M.M.: Facet-defining inequalities for the simple graph partitioning polytope. Discrete Optim. 4(2), 221\u2013231 (2007)","journal-title":"Discrete Optim."},{"key":"228_CR75","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.disopt.2017.03.001","volume":"25","author":"MM S\u00f8rensen","year":"2017","unstructured":"S\u00f8rensen, M.M.: Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes. Discrete Optim. 25, 120\u2013140 (2017)","journal-title":"Discrete Optim."},{"issue":"4","key":"228_CR76","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1145\/263867.263872","volume":"44","author":"M Stoer","year":"1997","unstructured":"Stoer, M., Wagner, F.: A simple min-cut algorithm. J. ACM 44(4), 585\u2013591 (1997)","journal-title":"J. ACM"},{"key":"228_CR77","unstructured":"STOM-Group: Hazmat network data (2021). https:\/\/github.com\/STOM-Group\/Hazmat-Network-Data. Last accessed June 2021"},{"key":"228_CR78","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-022-00221-5","volume":"1","author":"H Validi","year":"2022","unstructured":"Validi, H., Buchanan, A.: Political districting to minimize cut edges. Math. Program. Comput. 1, 1 (2022). https:\/\/doi.org\/10.1007\/s12532-022-00221-5","journal-title":"Math. Program. Comput."},{"issue":"2","key":"228_CR79","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1287\/opre.2021.2141","volume":"70","author":"H Validi","year":"2022","unstructured":"Validi, H., Buchanan, A., Lykhovyd, E.: Imposing contiguity constraints in political districting models. Oper. Res. 70(2), 867\u2013892 (2022)","journal-title":"Oper. Res."},{"issue":"4","key":"228_CR80","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1002\/net.21786","volume":"71","author":"C Vogiatzis","year":"2018","unstructured":"Vogiatzis, C., Walteros, J.L.: Integer programming models for detecting graph bipartitions with structural requirements. Networks 71(4), 432\u2013450 (2018)","journal-title":"Networks"},{"issue":"6","key":"228_CR81","doi-asserted-by":"publisher","first-page":"1866","DOI":"10.1287\/opre.2019.1970","volume":"68","author":"JL Walteros","year":"2020","unstructured":"Walteros, J.L., Buchanan, A.: Why is maximum clique often easy in practice? Oper. Res. 68(6), 1866\u20131895 (2020)","journal-title":"Oper. Res."},{"issue":"1","key":"228_CR82","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1002\/net.21834","volume":"73","author":"JL 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 73(1), 48\u201388 (2019)","journal-title":"Networks"},{"issue":"6684","key":"228_CR83","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 \u201csmall-world\u2019\u2019 networks. Nature 393(6684), 440\u2013442 (1998)","journal-title":"Nature"},{"issue":"2","key":"228_CR84","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ejor.2022.01.009","volume":"302","author":"N Wei","year":"2022","unstructured":"Wei, N., Walteros, J.L.: Integer programming methods for solving binary interdiction games. Eur. J. Oper. Res. 302(2), 456\u2013469 (2022)","journal-title":"Eur. J. Oper. Res."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-022-00228-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-022-00228-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-022-00228-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,25]],"date-time":"2023-02-25T13:27:50Z","timestamp":1677331670000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-022-00228-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,7]]},"references-count":84,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["228"],"URL":"https:\/\/doi.org\/10.1007\/s12532-022-00228-y","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,7]]},"assertion":[{"value":"4 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2022","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"}}]}}