{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T11:36:25Z","timestamp":1775302585752,"version":"3.50.1"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T00:00:00Z","timestamp":1410307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s10107-014-0811-z","type":"journal-article","created":{"date-parts":[[2014,9,9]],"date-time":"2014-09-09T04:15:14Z","timestamp":1410236114000},"page":"417-458","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["An exact combinatorial algorithm for minimum graph bisection"],"prefix":"10.1007","volume":"153","author":[{"given":"Daniel","family":"Delling","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Fleischman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Razenshteyn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,10]]},"reference":[{"key":"811_CR1","unstructured":"Armbruster, M.: Branch-and-cut for a semidefinite relaxation of large-scale minimum bisection problems. Ph.D. thesis, Technische Universit\u00e4t Chemnitz (2007)"},{"key":"811_CR2","unstructured":"Armbruster, M.: Graph bisection and equipartition (2007). http:\/\/www.tu-chemnitz.de\/mathematik\/discrete\/armbruster\/diss\/"},{"key":"811_CR3","doi-asserted-by":"crossref","unstructured":"Armbruster, M., F\u00fcgenschuh, M., Helmberg, C., Martin, A.: A comparative study of linear and semidefinite branch-and-cut methods for solving the minimum graph bisection problem. In: Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO), LNCS, vol. 5035, pp. 112\u2013124 (2008)","DOI":"10.1007\/978-3-540-68891-4_8"},{"issue":"3","key":"811_CR4","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s12532-012-0040-5","volume":"4","author":"M Armbruster","year":"2012","unstructured":"Armbruster, M., F\u00fcgenschuh, M., Helmberg, C., Martin, A.: LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison. Math. Progr. Comput. 4(3), 275\u2013306 (2012)","journal-title":"Math. Progr. Comput."},{"key":"811_CR5","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: Graph Partitioning and Graph Clustering\u201310th DIMACS Implementation Challenge Workshop, Contemporary Mathematics, vol. 588. American Mathematical Society and Center for Discrete Mathematics and Theoretical Computer Science (2013). http:\/\/www.cc.gatech.edu\/dimacs10\/","DOI":"10.1090\/conm\/588"},{"issue":"2","key":"811_CR6","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1002\/cpe.4330060203","volume":"6","author":"ST Barnard","year":"1994","unstructured":"Barnard, S.T., Simon, H.: Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurr. Comput. Pract. Exp. 6(2), 101\u2013117 (1994)","journal-title":"Concurr. Comput. Pract. Exp."},{"issue":"2.4","key":"811_CR7","first-page":"1","volume":"14","author":"R Bauer","year":"2009","unstructured":"Bauer, R., Delling, D.: SHARC: Fast and robust unidirectional routing. ACM J. Exp. Algorithmics 14(2.4), 1\u201329 (2009)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"2","key":"811_CR8","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(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"811_CR9","first-page":"243","volume":"78","author":"L Brunetta","year":"1997","unstructured":"Brunetta, L., Conforti, M., Rinaldi, G.: A branch-and-cut algorithm for the equicut problem. Math. Program. 78, 243\u2013263 (1997)","journal-title":"Math. Program."},{"key":"811_CR10","doi-asserted-by":"crossref","unstructured":"Budiu, M., Delling, D., Werneck, R.F.: DryadOpt: branch-and-bound on distributed data-parallel execution engines. In: Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1278\u20131289 (2011)","DOI":"10.1109\/IPDPS.2011.121"},{"issue":"2","key":"811_CR11","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"TN Bui","year":"1987","unstructured":"Bui, T.N., Chaudhuri, S., Leighton, F., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica 7(2), 171\u2013191 (1987)","journal-title":"Combinatorica"},{"issue":"12","key":"811_CR12","doi-asserted-by":"crossref","first-page":"1707","DOI":"10.1109\/TC.2007.70760","volume":"56","author":"P Chardaire","year":"2007","unstructured":"Chardaire, P., Barake, M., McKeown, G.P.: A PROBE-based heuristic for graph partitioning. IEEE Trans. Comput. 56(12), 1707\u20131720 (2007)","journal-title":"IEEE Trans. Comput."},{"key":"811_CR13","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1016\/j.parco.2007.12.001","volume":"34","author":"C Chevalier","year":"2008","unstructured":"Chevalier, C., Pellegrini, F.: PT-SCOTCH: a tool for efficient parallel graph ordering. Parallel Comput. 34, 318\u2013331 (2008)","journal-title":"Parallel Comput."},{"key":"811_CR14","doi-asserted-by":"crossref","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed parameter tractable. In: Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM, pp. 323\u2013332 (2014)","DOI":"10.1145\/2591796.2591852"},{"key":"811_CR15","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Proceedings of the International Symposium on Experimental Algorithms (SEA), LNCS, vol. 6630, pp. 376\u2013387. Springer, Berlin, Heidelberg (2011)","DOI":"10.1007\/978-3-642-20662-7_32"},{"key":"811_CR16","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Graph partitioning with natural cuts. In: Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1135\u20131146. IEEE (2011)","DOI":"10.1109\/IPDPS.2011.108"},{"key":"811_CR17","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Exact combinatorial branch-and-bound for graph bisection. In: Proceedings of the Algorithm Engineering and Experiments (ALENEX), pp. 30\u201344 (2012)","DOI":"10.1137\/1.9781611972924.3"},{"key":"811_CR18","doi-asserted-by":"crossref","unstructured":"Delling, D., Werneck, R.F.: Better bounds for graph bisection. In: Proceedings of the European Symposium on Algorithms (ESA), LNCS, vol. 7501, pp. 407\u2013418. Springer, Berlin, Heidelberg (2012)","DOI":"10.1007\/978-3-642-33090-2_36"},{"key":"811_CR19","doi-asserted-by":"crossref","unstructured":"Delling, D., Werneck, R.F.: Faster customization of road networks. In: Proceedings of the International Symposium on Experimental Algorithms (SEA), LNCS, vol. 7933, pp. 30\u201342. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-38527-8_5"},{"key":"811_CR20","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Contraction decomposition in $$h$$ h -minor-free graphs and algorithmic applications. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 441\u2013450 (2011)","DOI":"10.1145\/1993636.1993696"},{"key":"811_CR21","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074"},{"key":"811_CR22","doi-asserted-by":"crossref","unstructured":"Feldmann, A.E., Widmayer, P.: An $$O(n^4)$$ O ( n 4 ) time algorithm to compute the bisection width of solid grid graphs. In: Proceedings of the European Symposium on Algorithms (ESA), LNCS, vol. 6942, pp. 143\u2013154. Springer (2011)","DOI":"10.1007\/978-3-642-23719-5_13"},{"issue":"3\u20134","key":"811_CR23","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s10472-005-9001-2","volume":"45","author":"A Felner","year":"2005","unstructured":"Felner, A.: Finding optimal solutions to the graph partitioning problem with heuristic search. Ann. Math. Artif. Intell. 45(3\u20134), 293\u2013322 (2005)","journal-title":"Ann. Math. Artif. Intell."},{"key":"811_CR24","first-page":"229","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, 229\u2013256 (1998)","journal-title":"Math. Program."},{"key":"811_CR25","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of $${\\cal NP}$$ NP -Completeness. W. H. Freeman and Company, London (1979)"},{"key":"811_CR26","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified $${\\cal NP}$$ NP -complete graph problems. Theoret. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"811_CR27","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1287\/opre.42.6.1042","volume":"42","author":"B Gendron","year":"1994","unstructured":"Gendron, B., Crainic, T.G.: Parallel branch-and-bound algorithms: survey and synthesis. Oper. Res. 42(6), 1042\u20131066 (1994)","journal-title":"Oper. Res."},{"key":"811_CR28","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., Hed, S., Kaplan, H., Tarjan, R.E., Werneck, R.F.: Maximum flows by incremental breadth-first search. In: Proceedings of the European Symposium on Algorithms (ESA), LNCS, vol. 6942, pp. 457\u2013468. Springer (2011)","DOI":"10.1007\/978-3-642-23719-5_39"},{"issue":"4","key":"811_CR29","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"AV Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921\u2013940 (1988)","journal-title":"J. ACM"},{"key":"811_CR30","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/s10107-011-0503-x","volume":"137","author":"WW Hager","year":"2013","unstructured":"Hager, W.W., Phan, D.T., Zhang, H.: An exact algorithm for graph partitioning. Math. Program. 137, 531\u2013556 (2013)","journal-title":"Math. Program."},{"key":"811_CR31","unstructured":"Hein, M., B\u00fchler, T.: An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA. In: Proceedings Advances in Neural Information Processing Systems (NIPS), pp. 847\u2013855 (2010)"},{"key":"811_CR32","volume-title":"Sharpest Cut","author":"C Helmberg","year":"2004","unstructured":"Helmberg, C.: A cutting plane algorithm for large scale semidefinite relaxations. In: Gr\u00f6tschel, M. (ed.) Sharpest Cut. SIAM, Philadephia, PA (2004)"},{"issue":"2","key":"811_CR33","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1137\/0916028","volume":"16","author":"B Hendrickson","year":"1995","unstructured":"Hendrickson, B., Leland, R.: An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16(2), 452\u2013469 (1995)","journal-title":"SIAM J. Sci. Comput."},{"key":"811_CR34","doi-asserted-by":"crossref","unstructured":"Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Proceedings of the 1995 ACM\/IEEE Conference on Supercomputing, p. 28. ACM Press, New York (1995)","DOI":"10.1145\/224170.224228"},{"key":"811_CR35","doi-asserted-by":"crossref","unstructured":"Hilger, M., K\u00f6hler, E., M\u00f6hring, R.H., Schilling, H.: Fast point-to-point shortest path computations with arc-flags. In: Demetrescu et al. [21], pp. 41\u201372","DOI":"10.1090\/dimacs\/074\/03"},{"issue":"2.5","key":"811_CR36","first-page":"1","volume":"13","author":"M Holzer","year":"2008","unstructured":"Holzer, M., Schulz, F., Wagner, D.: Engineering multilevel overlay graphs for shortest-path queries. ACM J. Exp. Algorithmics 13(2.5), 1\u201326 (2008)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"811_CR37","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1137\/S009753970139567X","volume":"35","author":"K Jansen","year":"2005","unstructured":"Jansen, K., Karpinski, M., Lingas, A., Seidel, E.: Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. SIAM J. Comput. 35, 110\u2013119 (2005)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"811_CR38","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"DS Johnson","year":"1989","unstructured":"Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation; Part I. Graph partitioning. Oper. Res. 37(6), 865\u2013892 (1989)","journal-title":"Oper. Res."},{"key":"811_CR39","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01585164","volume":"62","author":"E Johnson","year":"1993","unstructured":"Johnson, E., Mehrotra, A., Nemhauser, G.: Min-cut clustering. Math. Program. 62, 133\u2013152 (1993)","journal-title":"Math. Program."},{"issue":"5","key":"811_CR40","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1109\/TKDE.2002.1033772","volume":"14","author":"S Jung","year":"2002","unstructured":"Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng. 14(5), 1029\u20131046 (2002)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"811_CR41","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF01582072","volume":"63","author":"M J\u00fcnger","year":"1994","unstructured":"J\u00fcnger, M., Martin, A., Reinelt, G., Weismantel, R.: Quadratic 0\/1 optimization and a decomposition approach for the placement of electronic circuits. Math. Program. 63, 257\u2013279 (1994)","journal-title":"Math. Program."},{"issue":"4","key":"811_CR42","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"DR Karger","year":"1996","unstructured":"Karger, D.R., Stein, C.: A new approach to the minimum cut problem. J. ACM 43(4), 601\u2013640 (1996)","journal-title":"J. ACM"},{"key":"811_CR43","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1287\/ijoc.12.3.177.12637","volume":"12","author":"SE Karisch","year":"2000","unstructured":"Karisch, S.E., Rendl, F., Clausen, J.: Solving graph bisection problems with semidefinite programming. INFORMS J. Comput. 12, 177\u2013191 (2000)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"811_CR44","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1999","unstructured":"Karypis, G., Kumar, G.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359\u2013392 (1999)","journal-title":"SIAM J. Sci. Comput."},{"key":"811_CR45","unstructured":"Koch, T., Martin, A., Vo\u00df, S.: SteinLib: An updated library on Steiner tree problems in graphs. Tech. Rep. 00\u201337, Konrad-Zuse-Zentrum Berlin (2000). http:\/\/elib.zib.de\/steinlib"},{"key":"811_CR46","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/882262.882264","volume":"22","author":"V Kwatra","year":"2003","unstructured":"Kwatra, V., Sch\u00f6dl, A., Essa, I., Turk, G., Bobick, A.: Graphcut textures: image and video synthesis using graph cuts. ACM Tr. Graphics 22, 277\u2013286 (2003)","journal-title":"ACM Tr. Graphics"},{"issue":"3","key":"811_CR47","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"AH Land","year":"1960","unstructured":"Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28(3), 497\u2013520 (1960)","journal-title":"Econometrica"},{"key":"811_CR48","doi-asserted-by":"crossref","unstructured":"Lang, K.J., Rao, S.: A flow-based method for improving the expansion or conductance of graph cuts. In: Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 325\u2013337 (2004)","DOI":"10.1007\/978-3-540-25960-2_25"},{"key":"811_CR49","doi-asserted-by":"crossref","unstructured":"Lauther, U.: An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In: Demetrescu et al. [21], pp. 19\u201340","DOI":"10.1090\/dimacs\/074\/02"},{"key":"811_CR50","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.: Applications of a planar separator theorem. SIAM J. Comput. 9, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"811_CR51","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: A system for large-scale graph processing. In: PODC, p. 6. ACM (2009)","DOI":"10.1145\/1583991.1584010"},{"key":"811_CR52","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K Mehlhorn","year":"1988","unstructured":"Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27, 125\u2013128 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"9","key":"811_CR53","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1016\/j.jpdc.2009.04.005","volume":"69","author":"H Meyerhenke","year":"2009","unstructured":"Meyerhenke, H., Monien, B., Sauerwald, T.: A new diffusion-based multilevel algorithm for computing graph partitions. J. Parallel Distrib. Comput. 69(9), 750\u2013761 (2009)","journal-title":"J. Parallel Distrib. Comput."},{"key":"811_CR54","doi-asserted-by":"crossref","unstructured":"Pellegrini, F., Roman, J.: SCOTCH: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In: High-Performance Computing and Networking, LNCS, vol. 1067, pp. 493\u2013498. Springer, New York (1996)","DOI":"10.1007\/3-540-61142-8_588"},{"key":"811_CR55","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 255\u2013263. ACM Press, New York (2008)","DOI":"10.1145\/1374376.1374415"},{"key":"811_CR56","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121, 307\u2013335 (2010)","journal-title":"Math. Program."},{"key":"811_CR57","doi-asserted-by":"crossref","unstructured":"Sander, P.V., Nehab, D., Chlamtac, E., Hoppe, H.: Efficient traversal of mesh edges using adjacency primitives. ACM Trans. Graphics 27, 144:1\u2013144:9 (2008)","DOI":"10.1145\/1409060.1409097"},{"key":"811_CR58","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: Proceedings of the Algorithm Engineering and Experiments (ALENEX), pp. 16\u201329. SIAM (2012)","DOI":"10.1137\/1.9781611972924.2"},{"key":"811_CR59","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schulz, C.: Think locally, act globally: Highly balanced graph partitioning. In: Proceedings of the International Symposium on Experimental Algorithms (SEA), LNCS, vol. 7933, pp. 164\u2013175. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-38527-8_16"},{"key":"811_CR60","doi-asserted-by":"crossref","unstructured":"Sellmann, M., Sensen, N., Timajev, L.: Multicommodity flow approximation used for exact graph partitioning. In: Proceedings of the European Symposium on Algorithms (ESA), LNCS, vol. 2832, pp. 752\u2013764. Springer (2003)","DOI":"10.1007\/978-3-540-39658-1_67"},{"key":"811_CR61","doi-asserted-by":"crossref","unstructured":"Sensen, N.: Lower bounds and exact algorithms for the graph partitioning problem using multicommodity flows. In: Proceedings of the European Symposium on Algorithms (ESA), LNCS, vol. 2161, pp. 391\u2013403. Springer (2001)","DOI":"10.1007\/3-540-44676-1_33"},{"issue":"8","key":"811_CR62","doi-asserted-by":"crossref","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":"2","key":"811_CR63","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1023\/B:JOGO.0000042115.44455.f3","volume":"29","author":"AJ Soper","year":"2004","unstructured":"Soper, A.J., Walshaw, C., Cross, M.: A combined evolutionary search and multilevel optimisation approach to graph partitioning. J. Global Optim. 29(2), 225\u2013241 (2004)","journal-title":"J. Global Optim."},{"key":"811_CR64","unstructured":"Soper, A.J., Walshaw, C., Cross, M.: The graph partitioning archive (2004). http:\/\/staffweb.cms.gre.ac.uk\/c.walshaw\/partition\/"},{"key":"811_CR65","doi-asserted-by":"crossref","unstructured":"Walshaw, C., Cross, M.: JOSTLE: Parallel multilevel graph-partitioning software \u2014 an overview. In: F. Magoul\u00e8s (ed.) Mesh Partitioning Techniques and Domain Decomposition Techniques, pp. 27\u201358. Civil-Comp Ltd., Edinburgh (2007)","DOI":"10.4203\/csets.17.2"},{"issue":"11","key":"811_CR66","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1109\/34.244673","volume":"15","author":"Z Wu","year":"1993","unstructured":"Wu, Z., Leahy, R.: An optimal graph theoretic approach to data clustering: theory and its application to image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 15(11), 1101\u20131113 (1993)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0811-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0811-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0811-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T16:14:17Z","timestamp":1565799257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0811-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,10]]},"references-count":66,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["811"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0811-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,10]]}}}