{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T12:03:17Z","timestamp":1762430597079},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T00:00:00Z","timestamp":1322611200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s10107-011-0503-x","type":"journal-article","created":{"date-parts":[[2011,11,29]],"date-time":"2011-11-29T05:45:06Z","timestamp":1322545506000},"page":"531-556","source":"Crossref","is-referenced-by-count":34,"title":["An exact algorithm for graph partitioning"],"prefix":"10.1007","volume":"137","author":[{"given":"William W.","family":"Hager","sequence":"first","affiliation":[]},{"given":"Dzung T.","family":"Phan","sequence":"additional","affiliation":[]},{"given":"Hongchao","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,11,30]]},"reference":[{"key":"503_CR1","unstructured":"Armbruster, M.: Branch-and-Cut for a Semidefinite Relaxation of Large-Scale Minimum Bisection Problems. PhD thesis, Chemnitz University of Technology, Chemnitz (2007)"},{"key":"503_CR2","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) Proceedings of the 13th International Integer Programming and Combinatorial Optimization Conference, vol. 5035 of Lecture Notes in Computer Science, pp. 112\u2013124. Springer, (2008)"},{"key":"503_CR3","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1093\/imanum\/8.1.141","volume":"8","author":"J. Barzilai","year":"1988","unstructured":"Barzilai J., Borwein J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141\u2013148 (1988)","journal-title":"IMA J. Numer. Anal."},{"issue":"1","key":"503_CR4","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1080\/10556789908805765","volume":"11","author":"B. Borchers","year":"1999","unstructured":"Borchers B.: CSDP, A C library for semidefinite programming. Optim. Methods Softw. 11(1), 613\u2013623 (1999)","journal-title":"Optim. Methods Softw."},{"key":"503_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. Math. Program. 78, 243\u2013263 (1997)","journal-title":"Math. Program."},{"key":"503_CR6","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1109\/71.780863","volume":"10","author":"U.V. Cataly\u00fcrek","year":"1999","unstructured":"Cataly\u00fcrek U.V., Aykanat C.: Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans. Parallel Distrib. Syst. 10, 673\u2013693 (1999)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"503_CR7","doi-asserted-by":"crossref","first-page":"931","DOI":"10.1145\/146585.146620","volume":"39","author":"O. Collins","year":"1992","unstructured":"Collins O., Dolinar S., McEliece R., Pollara F.: A VLSI decomposition of the de Bruijn graph. J. ACM 39, 931\u2013948 (1992)","journal-title":"J. ACM"},{"key":"503_CR8","unstructured":"de Souza, C.C.: The Graph Equipartition Problem: Optimal Solutions, Extensions and Applications. PhD thesis, Universit\u00e9 Catholique de Louvain, Louvain-la-Neuve (1993)"},{"key":"503_CR9","doi-asserted-by":"crossref","unstructured":"Devine, K., Boman, E., Heaphy, R., Bisseling, R., Catalyurek, U.: Parallel hypergraph partitioning for scientific computing. In: Proceedings of 20th International Parallel and Distributed Processing Symposium (IPDPS\u201906), IEEE (2006)","DOI":"10.1109\/IPDPS.2006.1639359"},{"key":"503_CR10","unstructured":"Dongarra, J.J.: Performance of various computers using standard linear equations software. Technical Report cs-89-85, University of Tennessee, Knoxville (2008)"},{"key":"503_CR11","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. 66, 211\u2013240 (1994)","journal-title":"Math. Program."},{"key":"503_CR12","doi-asserted-by":"crossref","unstructured":"Feldmann, R., Monien, B., Mysliwietz, P., Tsch\u00f6ke, S.: A better upper bound on the bisection width of de Bruijn networks. In: STACS 97, Lecture Notes in Computer Science, vol. 1200, pp. 511\u2013522. Springer, Berlin (1997)","DOI":"10.1007\/BFb0023485"},{"key":"503_CR13","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. Math. Program. 81, 229\u2013256 (1998)","journal-title":"Math. Program."},{"key":"503_CR14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey M.R., Johnson D.S., Stockmeyer L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"503_CR15","doi-asserted-by":"crossref","first-page":"2091","DOI":"10.1137\/S1064827594275339","volume":"19","author":"J.R. Gilbert","year":"1998","unstructured":"Gilbert J.R., Miller G.L., Teng S.H.: Geometric mesh partitioning: implementation and experiments. SIAM J. Sci. Comput. 19, 2091\u20132110 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"503_CR16","unstructured":"Grigori, L., Boman, E., Donfack, S., Davis, T.A.: Hypergraph-based unsymmetric nested dissection ordering for sparse LU factorization. SIAM J. Sci. Comput. (2008). under submission"},{"key":"503_CR17","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1137\/S0895480199335829","volume":"12","author":"W.W. Hager","year":"1999","unstructured":"Hager W.W., Krylyuk Y.: Graph partitioning and continuous quadratic programming. SIAM J. Discret. Math. 12, 500\u2013523 (1999)","journal-title":"SIAM J. Discret. Math."},{"key":"503_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s001860200173","volume":"55","author":"W.W. Hager","year":"2002","unstructured":"Hager W.W., Krylyuk Y.: Multiset graph partitioning. Math. Meth. Oper. Res. 55, 1\u201310 (2002)","journal-title":"Math. Meth. Oper. Res."},{"key":"503_CR19","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/080729165","volume":"20","author":"W.W. Hager","year":"2009","unstructured":"Hager W.W., Phan D.T.: An ellipsoidal branch and bound algorithm for global optimization. SIAM J. Optim. 20, 740\u2013758 (2009)","journal-title":"SIAM J. Optim."},{"key":"503_CR20","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1137\/1.9780898718805.ch15","volume-title":"The Sharpest Cut, MPS-SIAM Series Optimization","author":"C. Helmberg","year":"2004","unstructured":"Helmberg C.: A cutting plane algorithm for large scale semidefinite relaxations. In: Gr\u00f6tschel, M. (eds) The Sharpest Cut, MPS-SIAM Series Optimization, pp. 233\u2013256. SIAM, Philadelphia (2004)"},{"key":"503_CR21","doi-asserted-by":"crossref","unstructured":"Hendrickson, B., Leland, R.: The Chaco user\u2019s guide\u2014Version 2.0, Sandia National Laboratories. Technical Report SAND94-2692 (1994)","DOI":"10.2172\/10106339"},{"key":"503_CR22","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, 452\u2013469 (1995)","journal-title":"SIAM J. Sci. Comput."},{"key":"503_CR23","doi-asserted-by":"crossref","unstructured":"Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Proceedings of Supercomputing \u201995, ACM, November (1995)","DOI":"10.1145\/224170.224228"},{"key":"503_CR24","volume-title":"Introduction to Global Optimization","author":"R. Horst","year":"1995","unstructured":"Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Dordrecht (1995)"},{"key":"503_CR25","doi-asserted-by":"crossref","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. Oper. Res. 37, 865\u2013892 (1989)","journal-title":"Oper. Res."},{"key":"503_CR26","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01585164","volume":"62","author":"E.L. Johnson","year":"1993","unstructured":"Johnson E.L., Mehrotra A., Nemhauser G.L.: Min-cut clustering. Math. Program. 62, 133\u2013151 (1993)","journal-title":"Math. Program."},{"key":"503_CR27","doi-asserted-by":"crossref","unstructured":"Johnson, T.: A concurrent dynamic task graph. In: Proceedings of 1993 International Conference on Parallel Processing, (TR-93-011, CISE Department, University of Florida) (1993)","DOI":"10.1109\/ICPP.1993.18"},{"key":"503_CR28","doi-asserted-by":"crossref","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 J. Comput. 12, 177\u2013191 (2000)","journal-title":"INFORMS J. Comput."},{"key":"503_CR29","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G. Karypis","year":"1998","unstructured":"Karypis G., Kumar V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359\u2013392 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"503_CR30","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1137\/S0036144598334138","volume":"41","author":"G. Karypis","year":"1999","unstructured":"Karypis G., Kumar V.: Parallel multilevel k-way partitioning scheme for irregular graphs. SIAM Rev. 41, 278\u2013300 (1999)","journal-title":"SIAM Rev."},{"key":"503_CR31","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1155\/2000\/19436","volume":"11","author":"G. Karypis","year":"2000","unstructured":"Karypis G., Kumar V.: Multilevel k-way hypergraph partitioning. VLSI Des. 11, 285\u2013300 (2000)","journal-title":"VLSI Des."},{"key":"503_CR32","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"T. Lengauer","year":"1990","unstructured":"Lengauer T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chichester (1990)"},{"key":"503_CR33","unstructured":"Mitchell, J.: Branch-and-cut for the k-way equipartition problem. Technical report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute (2001)"},{"key":"503_CR34","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"K.G. Murty","year":"1987","unstructured":"Murty K.G., Kabadi S.N.: Some NP-complete problems in quadratic and linear programming. Math. Program. 39, 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"503_CR35","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00120662","volume":"1","author":"P.M. Pardalos","year":"1991","unstructured":"Pardalos P.M., Vavasis S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1, 15\u201322 (1991)","journal-title":"J. Glob. Optim."},{"key":"503_CR36","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1002\/(SICI)1096-9128(200002\/03)12:2\/3<69::AID-CPE472>3.0.CO;2-W","volume":"12","author":"F. Pellegrini","year":"2000","unstructured":"Pellegrini F., Roman J., Amestoy P.R.: Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering. Concurr. Pract. Exp. 12, 68\u201384 (2000)","journal-title":"Concurr. Pract. Exp."},{"key":"503_CR37","unstructured":"Preis, R., Diekmann, R.: The PARTY partitioning library user guide\u2014version 1.1 (1996)"},{"key":"503_CR38","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":"503_CR39","doi-asserted-by":"crossref","unstructured":"Sensen, N.: Lower bounds and exact algorithms for the graph partitioning problem using multicommodity flows. In: Lecture Notes in Computer Science, vol. 2161, pp. 391\u2013403. Springer, London (2001)","DOI":"10.1007\/3-540-44676-1_33"},{"key":"503_CR40","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/S0377-2217(86)80006-6","volume":"27","author":"M. Sinclair","year":"1986","unstructured":"Sinclair M.: An exact penalty function approach for nonlinear integer programming problems. Eur. J. Oper. Res. 27, 50\u201356 (1986)","journal-title":"Eur. J. Oper. Res."},{"key":"503_CR41","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1023\/B:JOGO.0000042115.44455.f3","volume":"29","author":"A.J. Soper","year":"2004","unstructured":"Soper A.J., Walshaw C., Cross M.: A combined multilevel search and multilevel optimization approach to graph-partition. J. Glob. Optim. 29, 225\u2013241 (2004)","journal-title":"J. Glob. Optim."},{"key":"503_CR42","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/0045-7825(94)90137-6","volume":"111","author":"C. Souza","year":"1994","unstructured":"Souza C., Keunings R., Wolsey L., Zone O.: A new approach to minimizing the frontwidth in finite element calculations. Comput. Methods Appl. Mech. Eng. 111, 323\u2013334 (1994)","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"503_CR43","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1137\/S1064827595288942","volume":"19","author":"S.-H. Teng","year":"1998","unstructured":"Teng S.-H.: Provably good partitioning and load balancing algorithms for parallel adaptive N-body simulation. SIAM J. Sci. Comput. 19, 635\u2013656 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"503_CR44","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1006\/jpdc.1997.1407","volume":"47","author":"C. Walshaw","year":"1997","unstructured":"Walshaw C., Cross M., Everett M.: Parallel dynamic graph partitioning for adaptive unstructured meshs. J. Parallel Distrib. Comput. 47, 102\u2013108 (1997)","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-011-0503-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-011-0503-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-011-0503-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,28]],"date-time":"2020-06-28T02:23:57Z","timestamp":1593311037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-011-0503-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,30]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["503"],"URL":"https:\/\/doi.org\/10.1007\/s10107-011-0503-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,30]]}}}