{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T12:23:42Z","timestamp":1770985422226,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T00:00:00Z","timestamp":1564531200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T00:00:00Z","timestamp":1564531200000},"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":["Math. Prog. Comp."],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s12532-019-00167-1","type":"journal-article","created":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T16:02:43Z","timestamp":1564588963000},"page":"133-164","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["On integer and bilevel formulations for the k-vertex cut problem"],"prefix":"10.1007","volume":"12","author":[{"given":"Fabio","family":"Furini","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4834-6284","authenticated-orcid":false,"given":"Ivana","family":"Ljubi\u0107","sequence":"additional","affiliation":[]},{"given":"Enrico","family":"Malaguti","sequence":"additional","affiliation":[]},{"given":"Paolo","family":"Paronuzzi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,31]]},"reference":[{"issue":"3","key":"167_CR1","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s10107-005-0574-7","volume":"103","author":"E Balas","year":"2005","unstructured":"Balas, E., de Souza, C.C.: The vertex separator problem: a polyhedral investigation. Math. Program. 103(3), 583\u2013608 (2005)","journal-title":"Math. Program."},{"issue":"3","key":"167_CR2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0167-6377(99)00071-1","volume":"26","author":"F Barahona","year":"2000","unstructured":"Barahona, F.: On the k-cut problem. Oper. Res. Lett. 26(3), 99\u2013105 (2000)","journal-title":"Oper. Res. Lett."},{"key":"167_CR3","unstructured":"Bastubbe, M., L\u00fcbbecke, M.: A branch-and-price algorithm for capacitated hypergraph vertex separation. Technical Report, Optimization (2017)"},{"issue":"1","key":"167_CR4","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1002\/net.20478","volume":"59","author":"W Ben-Ameur","year":"2012","unstructured":"Ben-Ameur, W., Biha, M.D.: On the minimum cut separator problem. Networks 59(1), 30\u201336 (2012)","journal-title":"Networks"},{"key":"167_CR5","first-page":"337","volume-title":"Lecture Notes in Computer Science","author":"Walid Ben-Ameur","year":"2013","unstructured":"Ben-Ameur, W., Mohamed-Sidi, M.A., Neto, J.: The k-separator problem. In: Computing and Combinatorics, pp. 337\u2013348 (2013)"},{"issue":"2","key":"167_CR6","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1002\/net.21534","volume":"63","author":"A Berger","year":"2014","unstructured":"Berger, A., Grigoriev, A., v.\u00a0d. Zwaan, R.: Complexity and approximability of the k-way vertex cut. Networks 63(2), 170\u2013178 (2014)","journal-title":"Networks"},{"issue":"1","key":"167_CR7","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1137\/S1052623497318682","volume":"9","author":"R Bornd\u00f6rfer","year":"1998","unstructured":"Bornd\u00f6rfer, R., Ferreira, C., Martin, A.: Decomposing matrices into blocks. SIAM J. Optim. 9(1), 236\u2013269 (1998)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"167_CR8","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1287\/inte.1060.0252","volume":"36","author":"G Brown","year":"2006","unstructured":"Brown, G., Carlyle, M., Salmer\u00f3n, J., Wood, K.: Defending critical infrastructure. INFORMS J. Appl. Anal. 36(6), 530\u2013544 (2006)","journal-title":"INFORMS J. Appl. Anal."},{"issue":"3","key":"167_CR9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0020-0190(92)90140-Q","volume":"42","author":"TN Bui","year":"1992","unstructured":"Bui, T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inf. Process. Lett. 42(3), 153\u2013159 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"167_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/net.3230210106","volume":"21","author":"S Chopra","year":"1991","unstructured":"Chopra, S., Rao, M.R.: On the multiway cut polyhedron. Networks 21(1), 51\u201389 (1991)","journal-title":"Networks"},{"key":"167_CR11","unstructured":"Color02\/03\/04: graph coloring and its generalizations. http:\/\/mat.gsia.cmu.edu\/COLOR03\/ . Accessed 20 July 2018"},{"key":"167_CR12","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.disopt.2018.07.003","volume":"31","author":"D Cornaz","year":"2019","unstructured":"Cornaz, D., Furini, F., Lacroix, M., Malaguti, E., Mahjoub, A.R., Martin, S.: The vertex $$k$$-cut problem. Discrete Optim. 31, 8\u201328 (2019)","journal-title":"Discrete Optim."},{"key":"167_CR13","doi-asserted-by":"crossref","unstructured":"Cornaz, D., Magnouche, Y., Mahjoub, A.R., Martin, S.: The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut. In: Conference on Computers and Industrial Engineering (CIE45), pp. 857\u2013864 (2015)","DOI":"10.1109\/CoDIT.2016.7593645"},{"issue":"4","key":"167_CR14","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakiss, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"167_CR15","unstructured":"Dimacs implementation challenges. http:\/\/dimacs.rutgers.edu\/archive\/Challenges\/ . Accessed 20 July 2018"},{"issue":"3","key":"167_CR16","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/s10107-005-0573-8","volume":"103","author":"C de Souza","year":"2005","unstructured":"de Souza, C., Balas, E.: The vertex separator problem: algorithms and computations. Math. Program. 103(3), 609\u2013631 (2005)","journal-title":"Math. Program."},{"issue":"2","key":"167_CR17","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2002)","journal-title":"Math. Program."},{"issue":"2","key":"167_CR18","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1287\/ijoc.2018.0831","volume":"31","author":"M Fischetti","year":"2019","unstructured":"Fischetti, M., Ljubi\u0107, I., Monaci, M., Sinnl, M.: Interdiction games under monotonicity. INFORMS J. Comput. 31(2), 390\u2013410 (2019)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"167_CR19","doi-asserted-by":"crossref","first-page":"317","DOI":"10.7155\/jgaa.00130","volume":"10","author":"J Fukuyama","year":"2006","unstructured":"Fukuyama, J.: NP-completeness of the planar separator problems. J. Gr. Algorithms Appl. 10(2), 317\u2013328 (2006)","journal-title":"J. Gr. Algorithms Appl."},{"issue":"1","key":"167_CR20","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.ejor.2019.02.028","volume":"277","author":"F Furini","year":"2019","unstructured":"Furini, F., Ljubi\u0107, I., San Segundo, P., Martin, S.: The maximum clique interdiction problem. Eur. J. Oper. Res. 277(1), 112\u2013127 (2019)","journal-title":"Eur. J. Oper. Res."},{"key":"167_CR21","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/3-540-58201-0_92","volume-title":"Automata, Languages and Programming","author":"Naveen Garg","year":"1994","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in directed and node weighted graphs. In: Automata, Languages and Programming, pp. 487\u2013498 (1994)"},{"issue":"1","key":"167_CR22","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N Garg","year":"2004","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50(1), 49\u201361 (2004)","journal-title":"J. Algorithms"},{"issue":"1","key":"167_CR23","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"167_CR24","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: An FPT algorithm beating 2-approximation for $$k$$-cut. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201918, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp. 2821\u20132837 (2018)","DOI":"10.1137\/1.9781611975031.179"},{"issue":"1","key":"167_CR25","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/S0097539794273083","volume":"26","author":"DR Karger","year":"1997","unstructured":"Karger, D.R., Motwani, R.: An NC algorithm for minimum cuts. SIAM J. Comput. 26(1), 255\u2013272 (1997)","journal-title":"SIAM J. Comput."},{"key":"167_CR26","doi-asserted-by":"crossref","first-page":"1127","DOI":"10.1007\/11523468_91","volume-title":"Automata, Languages and Programming","author":"D Kempe","year":"2005","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Influential nodes in a diffusion model for social networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) Automata, Languages and Programming, pp. 1127\u20131138. Springer, Berlin (2005)"},{"key":"167_CR27","doi-asserted-by":"crossref","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."},{"key":"167_CR28","doi-asserted-by":"crossref","unstructured":"Magnouche, J.: The Multi-terminal Vertex Separator Problem: Complexity, Polyhedra and Algorithms (2017)","DOI":"10.1007\/978-3-319-45587-7_28"},{"issue":"3","key":"167_CR29","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"167_CR30","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.: Finding $$k$$ cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J. Comput."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-019-00167-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-019-00167-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-019-00167-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T23:26:12Z","timestamp":1664061972000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-019-00167-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,31]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["167"],"URL":"https:\/\/doi.org\/10.1007\/s12532-019-00167-1","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,31]]},"assertion":[{"value":"25 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}