{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:02:28Z","timestamp":1761292948948},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_36","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"407-418","source":"Crossref","is-referenced-by-count":9,"title":["Better Bounds for Graph Bisection"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Delling","sequence":"first","affiliation":[]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","unstructured":"Armbruster, M.: Branch-and-Cut for a Semidefinite Relaxation of Large-Scale Minimum Bisection Problems. PhD thesis, Technische Universit\u00e4t Chemnitz (2007)"},{"key":"36_CR2","unstructured":"Armbruster, M.: Graph Bisection and Equipartition (2007), \n                  \n                    http:\/\/www.tu-chemnitz.de\/mathematik\/discrete\/armbruster\/diss\/"},{"key":"36_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-540-68891-4_8","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. Armbruster","year":"2008","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: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 112\u2013124. Springer, Heidelberg (2008)"},{"key":"36_CR4","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: 10th DIMACS Implementation Challenge: Graph Partitioning and Graph Clustering (2011), \n                  \n                    http:\/\/www.cc.gatech.edu\/dimacs10\/index.shtml"},{"key":"36_CR5","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. Mathematical Programming\u00a078, 243\u2013263 (1997)","journal-title":"Mathematical Programming"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"Budiu, M., Delling, D., Werneck, R.F.: DryadOpt: Branch-and-bound on distributed data-parallel execution engines. In: IPDPS, pp. 1278\u20131289 (2011)","DOI":"10.1109\/IPDPS.2011.121"},{"issue":"2","key":"36_CR7","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T.N. Bui","year":"1987","unstructured":"Bui, T.N., Chaudhuri, S., Leighton, F., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica\u00a07(2), 171\u2013191 (1987)","journal-title":"Combinatorica"},{"key":"36_CR8","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Exact combinatorial branch-and-bound for graph bisection. In: ALENEX, pp. 30\u201344 (2012)","DOI":"10.1137\/1.9781611972924.3"},{"key":"36_CR9","first-page":"229","volume":"81","author":"C.E. 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. Mathematical Programming\u00a081, 229\u2013256 (1998)","journal-title":"Mathematical Programming"},{"key":"36_CR10","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of \n                  \n                    \n                  \n                  $\\mathcal{NP}$\n                -Completeness. W.H. Freeman and Company (1979)"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Hager, W.W., Phan, D.T., Zhang, H.: An exact algorithm for graph partitioning. Mathematical Programming, 1\u201326 (2011)","DOI":"10.1007\/s10107-011-0503-x"},{"issue":"6","key":"36_CR12","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"D.S. 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. Operations Research\u00a037(6), 865\u2013892 (1989)","journal-title":"Operations Research"},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/ijoc.12.3.177.12637","volume":"12","author":"S.E. Karisch","year":"2000","unstructured":"Karisch, S.E., Rendl, F., Clausen, J.: Solving graph bisection problems with semidefinite programming. INFORMS Journal on Computing\u00a012, 177\u2013191 (2000)","journal-title":"INFORMS Journal on Computing"},{"issue":"1","key":"36_CR14","doi-asserted-by":"publisher","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. Scientific Computing\u00a020(1), 359\u2013392 (1999)","journal-title":"SIAM J. Scientific Computing"},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"Koch, T., Martin, A., Vo\u00df, S.: SteinLib: An updated library on Steiner tree problems in graphs. Technical Report 00-37, Konrad-Zuse-Zentrum Berlin (2000)","DOI":"10.1007\/978-1-4613-0255-1_9"},{"issue":"3","key":"36_CR16","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"A.H. Land","year":"1960","unstructured":"Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica\u00a028(3), 497\u2013520 (1960)","journal-title":"Econometrica"},{"key":"36_CR17","doi-asserted-by":"publisher","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. Programming\u00a0121, 307\u2013335 (2010)","journal-title":"Math. Programming"},{"key":"36_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1409060.1409097","volume":"27","author":"P.V. Sander","year":"2008","unstructured":"Sander, P.V., Nehab, D., Chlamtac, E., Hoppe, H.: Efficient traversal of mesh edges using adjacency primitives. ACM Trans. on Graphics\u00a027, 144:1\u2013144:9 (2008)","journal-title":"ACM Trans. on Graphics"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: ALENEX, pp. 16\u201329. SIAM (2012)","DOI":"10.1137\/1.9781611972924.2"},{"key":"36_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1007\/978-3-540-39658-1_67","volume-title":"Algorithms - ESA 2003","author":"M. Sellmann","year":"2003","unstructured":"Sellmann, M., Sensen, N., Timajev, L.: Multicommodity Flow Approximation Used for Exact Graph Partitioning. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 752\u2013764. Springer, Heidelberg (2003)"},{"key":"36_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/3-540-44676-1_33","volume-title":"Algorithms - ESA 2001","author":"N. Sensen","year":"2001","unstructured":"Sensen, N.: Lower Bounds and Exact Algorithms for the Graph Partitioning Problem Using Multicommodity Flows. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 391\u2013403. Springer, Heidelberg (2001)"},{"key":"36_CR22","unstructured":"Soper, A.J., Walshaw, C., Cross, M.: The Graph Partitioning Archive (2004), \n                  \n                    http:\/\/staffweb.cms.gre.ac.uk\/~c.walshaw\/partition\/"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:55Z","timestamp":1620129295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}