{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T12:29:46Z","timestamp":1770294586577,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T00:00:00Z","timestamp":1505692800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s10589-017-9943-4","type":"journal-article","created":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T15:53:03Z","timestamp":1505749983000},"page":"159-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["The min-cut and vertex separator problem"],"prefix":"10.1007","volume":"69","author":[{"given":"Fanz","family":"Rendl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renata","family":"Sotirov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,18]]},"reference":[{"key":"9943_CR1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"9943_CR2","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"9943_CR3","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"SN Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"9943_CR4","unstructured":"Fu, B., Oprisan, S.A., Xu, L.: Multi-directional width-bounded geometric separator and protein folding. Int. J. Comput. Geom. Appl. 18(5), 389\u2013413 (2008)"},{"key":"9943_CR5","volume-title":"Complexity Issues in VLSI: Optimal Layout for the Shuffle-Exchange Graph and Other Networks","author":"FT Leighton","year":"1983","unstructured":"Leighton, F.T.: Complexity Issues in VLSI: Optimal Layout for the Shuffle-Exchange Graph and Other Networks. MIT Press, Cambridge, MA (1983)"},{"issue":"2","key":"9943_CR6","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/S1064827594262613","volume":"19","author":"GL Miller","year":"1998","unstructured":"Miller, G.L., Teng, S.-H., Thurstons, W., Vavasis, S.A.: Geometric separators for finite-element meshes. SIAM J. Sci. Comput. 19(2), 364\u2013386 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2","key":"9943_CR7","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"9943_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"9943_CR9","volume-title":"Kronecker Products and Matrix Calculus with Applications","author":"A Graham","year":"1981","unstructured":"Graham, A.: Kronecker Products and Matrix Calculus with Applications. Ellis Horwood Ltd., Chichester (1981)"},{"key":"9943_CR10","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1147\/rd.175.0420","volume":"17","author":"WE Donath","year":"1973","unstructured":"Donath, W.E., Hoffman, A.J.: Lower bounds for the partitioning of graphs. IBM J. Res. Dev. 17, 420\u2013425 (1973)","journal-title":"IBM J. Res. Dev."},{"issue":"3","key":"9943_CR11","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02032130","volume":"58","author":"F Rendl","year":"1995","unstructured":"Rendl, F., Wolkowicz, H.: A projection technique for partitioning the nodes of a graph. Ann. Oper. Res. 58(3), 155\u2013179 (1995)","journal-title":"Ann. Oper. Res."},{"key":"9943_CR12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1080\/03081089508818381","volume":"39","author":"C Helmberg","year":"1995","unstructured":"Helmberg, C., Mohar, B., Poljak, S., Rendl, F.: A spectral approach to bandwidth and separator problems in graphs. Linear Multilinear Algebra 39, 73\u201390 (1995)","journal-title":"Linear Multilinear Algebra"},{"key":"9943_CR13","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF01581147","volume":"66","author":"J Falkner","year":"1994","unstructured":"Falkner, J., Rendl, F., Wolkowicz, H.: A computational study of graph partitioning. Math. Program. Ser. B 66, 211\u2013239 (1994)","journal-title":"Math. Program. Ser. B"},{"issue":"2","key":"9943_CR14","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s10589-015-9779-8","volume":"63","author":"TK Pong","year":"2016","unstructured":"Pong, T.K., Sun, H., Wang, N., Wolkowicz, H.: Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem. Comput. Optim. Appl. 63(2), 333\u2013364 (2016)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"9943_CR15","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/S0895479898340299","volume":"22","author":"KM Anstreicher","year":"2000","unstructured":"Anstreicher, K.M., Wolkowicz, H.: On Lagrangian relaxation of quadratic matrix constraints. SIAM J. Matrix Anal. Appl. 22(1), 41\u201355 (2000)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9943_CR16","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/050637467","volume":"18","author":"J Povh","year":"2007","unstructured":"Povh, J., Rendl, F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18, 223\u2013241 (2007)","journal-title":"SIAM J. Optim."},{"key":"9943_CR17","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1023\/A:1009795911987","volume":"2","author":"Q Zhao","year":"1998","unstructured":"Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2, 71\u2013109 (1998)","journal-title":"J. Comb. Optim."},{"issue":"97","key":"9943_CR18","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/S0166-218X(99)00102-X","volume":"96","author":"W Wolkowicz","year":"1999","unstructured":"Wolkowicz, W., Zhao, Q.: Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96(97), 461\u2013479 (1999)","journal-title":"Discrete Appl. Math."},{"key":"9943_CR19","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1287\/ijoc.2014.0611","volume":"27","author":"ER Dam van","year":"2014","unstructured":"van Dam, E.R., Sotirov, R.: On bounding the bandwidth of graphs with symmetry. INFORMS J. Comput. 27, 75\u201388 (2014)","journal-title":"INFORMS J. Comput."},{"key":"9943_CR20","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. Ser. B 103, 583\u2013608 (2005)","journal-title":"Math. Program. Ser. B"},{"key":"9943_CR21","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/s10107-005-0573-8","volume":"103","author":"CC Souza de","year":"2005","unstructured":"de Souza, C.C., Balas, E.: The vertex separator problem: algorithms and computations. Math. Program. Ser. B 103, 609\u2013631 (2005)","journal-title":"Math. Program. Ser. B"},{"key":"9943_CR22","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s10898-010-9568-y","volume":"49","author":"MD Biha","year":"2011","unstructured":"Biha, M.D., Meurs, M.J.: An exact algorithm for solving the vertex separator problem. J. Glob. Optim. 49, 425\u2013434 (2011)","journal-title":"J. Glob. Optim."},{"key":"9943_CR23","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/j.ejor.2014.05.042","volume":"240","author":"WW Hager","year":"2015","unstructured":"Hager, W.W., Hungerford, J.T.: A continuous quadratic programming formulation of the vertex separator problem. Eur. J. Oper. Res. 240, 328\u2013337 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"9943_CR24","doi-asserted-by":"publisher","unstructured":"Hager, W.W., Hungerford, J.T., Safro, I.: A multilevel bilinear programming algorithm for the vertex separator problem. Comput. Optim. Appl. (2017). doi:\n                        10.1007\/s10589-017-9945-2","DOI":"10.1007\/s10589-017-9945-2"},{"key":"9943_CR25","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/s101070100255","volume":"91","author":"KM Anstreicher","year":"2002","unstructured":"Anstreicher, K.M., Brixius, N., Goux, J.-P., Linderoth, J.: Solving large quadratic assignment problems on computational grids. Math. Program. Ser. B 91, 563\u2013588 (2002)","journal-title":"Math. Program. Ser. B"},{"issue":"3","key":"9943_CR26","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/PL00011402","volume":"89","author":"KM Anstreicher","year":"2001","unstructured":"Anstreicher, K.M., Brixius, N.W.: A new bound for the quadratic assignment problem based on convex quadratic programming. Math. Program. Ser. A 89(3), 341\u2013357 (2001)","journal-title":"Math. Program. Ser. A"},{"issue":"3","key":"9943_CR27","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s12532-012-0040-5","volume":"4","author":"M Armbruster","year":"2012","unstructured":"Armbruster, M., Helmberg, C., F\u00fcgenschuh, M., Martin, A.: LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison. Math. Program. Comput. 4(3), 275\u2013306 (2012)","journal-title":"Math. Program. Comput."},{"issue":"3","key":"9943_CR28","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A Hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"9943_CR29","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"MW Padberg","year":"1989","unstructured":"Padberg, M.W.: The boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139\u2013172 (1989)","journal-title":"Math. Program."},{"key":"9943_CR30","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1051\/ro\/197004V300671","volume":"3","author":"PL Hammer","year":"1970","unstructured":"Hammer, P.L., Rubin, A.A.: Some remarks on quadratic programming with 0\u20131 variables. RAIRO 3, 67\u201379 (1970)","journal-title":"RAIRO"},{"key":"9943_CR31","first-page":"1","volume":"25","author":"NZ Shor","year":"1987","unstructured":"Shor, N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1\u201311 (1987)","journal-title":"Sov. J. Comput. Syst. Sci."},{"key":"9943_CR32","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/BF00122430","volume":"2","author":"NZ Shor","year":"1992","unstructured":"Shor, N.Z.: Dual estimates in multiextremal problems. J. Glob. Optim. 2, 411\u2013418 (1992)","journal-title":"J. Glob. Optim."},{"key":"9943_CR33","unstructured":"Lemarechal, C., Oustry, F.: Semidefinite Relaxations and Lagrangian Duality with Application to Combinatorial Optimization. Research Report 3710, INRIA, Rhones-Alpes (1999)"},{"key":"9943_CR34","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s10288-006-0011-7","volume":"5","author":"A Faye","year":"2007","unstructured":"Faye, A., Roupin, F.: Partial Lagrangian relaxation for general quadratic programming. 4OR Q. J Oper. Res. 5, 75\u201388 (2007)","journal-title":"4OR Q. J Oper. Res."},{"issue":"6","key":"9943_CR35","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1016\/j.dam.2007.12.007","volume":"157","author":"A Billionnet","year":"2009","unstructured":"Billionnet, A., Elloumi, S., Plateau, M.: Improving the performance of standard solvers for quadratic 0\u20131 programs by a tight convex reformulation: the QCR method. Discrete Appl. Math. 157(6), 1185\u20131197 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9943_CR36","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10107-008-0246-5","volume":"122","author":"E Klerk De","year":"2010","unstructured":"De Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. Ser. A 122(2), 225\u2013246 (2010)","journal-title":"Math. Program. Ser. A"},{"issue":"2","key":"9943_CR37","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s10107-012-0603-2","volume":"136","author":"E Klerk De","year":"2012","unstructured":"De Klerk, E., Pasechnik, D.V., Sotirov, R., Dobre, C.: On semidefinite programming relaxations of maximum \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -section. Math. Program. Ser. B 136(2), 253\u2013278 (2012)","journal-title":"Math. Program. Ser. B"},{"key":"9943_CR38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.11.003","volume":"60","author":"U Feige","year":"2006","unstructured":"Feige, U., Langberg, M.: The RPR\n                        $$^2$$\n                        \n                            \n                                \n                                    \n                                    2\n                                \n                            \n                        \n                     rounding technique for semidefinite programs. J. Algorithms 60, 1\u201323 (2006)","journal-title":"J. Algorithms"},{"issue":"2","key":"9943_CR39","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"BW Kernighan","year":"1970","unstructured":"Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291\u2013307 (1970)","journal-title":"Bell Syst. Tech. J."},{"key":"9943_CR40","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"RH T\u00fct\u00fcnc\u00fc","year":"2003","unstructured":"T\u00fct\u00fcnc\u00fc, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. Ser. B 95, 189\u2013217 (2003)","journal-title":"Math. Program. Ser. B"},{"key":"9943_CR41","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-1-5041-2940-4_9","volume-title":"The Quality of Numerical Software: Assessment and Enhancement","author":"R Boisvert","year":"1997","unstructured":"Boisvert, R., Pozo, R., Remington, K., Barrett, R., Dongarra, J.: Matrix market: a web resource for test matrix collections. In: Boisvert, R. (ed.) The Quality of Numerical Software: Assessment and Enhancement, pp. 125\u2013137. Chapman and Hall, London (1997)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-017-9943-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-017-9943-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-017-9943-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,1,3]],"date-time":"2018-01-03T13:01:56Z","timestamp":1514984516000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-017-9943-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,18]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9943"],"URL":"https:\/\/doi.org\/10.1007\/s10589-017-9943-4","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,18]]}}}