{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T22:14:20Z","timestamp":1743113660643,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031609237"},{"type":"electronic","value":"9783031609244"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-60924-4_4","type":"book-chapter","created":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T03:38:27Z","timestamp":1716349107000},"page":"43-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Family of\u00a0Spanning-Tree Formulations for\u00a0the\u00a0Maximum Cut Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5335-0678","authenticated-orcid":false,"given":"Sven","family":"Mallach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,22]]},"reference":[{"issue":"3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F Barahona","year":"1988","unstructured":"Barahona, F., Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493\u2013513 (1988)","journal-title":"Oper. Res."},{"issue":"1","key":"4_CR2","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01587084","volume":"44","author":"F Barahona","year":"1989","unstructured":"Barahona, F., J\u00fcnger, M., Reinelt, G.: Experiments in quadratic 0\u20131 programming. Math. Program. 44(1), 127\u2013137 (1989)","journal-title":"Math. Program."},{"issue":"2","key":"4_CR3","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F Barahona","year":"1986","unstructured":"Barahona, F., Mahjoub, A.R.: On the cut polytope. Math. Program. 36(2), 157\u2013173 (1986)","journal-title":"Math. Program."},{"issue":"1","key":"4_CR4","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10107-005-0637-9","volume":"109","author":"A Billionnet","year":"2007","unstructured":"Billionnet, A., Elloumi, S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0\u20131 problem. Math. Program. 109(1), 55\u201368 (2007)","journal-title":"Math. Program."},{"key":"4_CR5","unstructured":"Biq Mac Library \u2013 Binary quadratic and Max cut Library (2009). https:\/\/biqmac.aau.at\/biqmaclib.html"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10107-013-0688-2","volume":"146","author":"T Bonato","year":"2013","unstructured":"Bonato, T., J\u00fcnger, M., Reinelt, G., Rinaldi, G.: Lifting and separation procedures for the cut polytope. Math. Program. A 146, 351\u2013378 (2013)","journal-title":"Math. Program. A"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Charfreitag, J.,\u00a0J\u00fcnger, M.,\u00a0Mallach, S.,\u00a0Mutzel, P.: McSparse: exact solutions of sparse maximum cut and sparse unconstrained binary quadratic optimization problems. In: Phillips, C.A.,\u00a0Speckmann, B. (eds.) 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pp. 54\u201366. SIAM (2022)","DOI":"10.1137\/1.9781611977042.5"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Charfreitag, J.,\u00a0Mallach, S.,\u00a0Mutzel, P.: Integer programming for the maximum cut problem: a refined model and implications for branching. In:\u00a0Berry, J., Shmoys, D.B. (eds.) Proceedings of the 2023 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23), pp. 63\u201374 (2023)","DOI":"10.1137\/1.9781611977714.6"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0012-365X(90)90056-N","volume":"79","author":"C De Simone","year":"1990","unstructured":"De Simone, C.: The cut polytope and the Boolean quadric polytope. Disc. Math. 79(1), 71\u201375 (1990)","journal-title":"Disc. Math."},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-38221-5_26","volume-title":"Graph-Based Representations in Pattern Recognition","author":"S de Sousa","year":"2013","unstructured":"de Sousa, S., Haxhimusa, Y., Kropatsch, W.G.: Estimation of distribution algorithm for the max-cut problem. In: Kropatsch, W.G., Artner, N.M., Haxhimusa, Y., Jiang, X. (eds.) GbRPR 2013. LNCS, vol. 7877, pp. 244\u2013253. Springer, Heidelberg (2013)"},{"issue":"3","key":"4_CR11","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"PL Hammer","year":"1965","unstructured":"Hammer, P.L.: Some network flow problems solved with pseudo-Boolean programming. Oper. Res. 13(3), 388\u2013399 (1965)","journal-title":"Oper. Res."},{"key":"4_CR12","unstructured":"J\u00fcnger, M.,\u00a0Mallach, S.: Odd-cycle separation for maximum cut and binary quadratic optimization. In: Bender, M.A.,\u00a0Svensson, O.,\u00a0Herman, G. (eds.) 27th Annual European Symposium on Algorithms (ESA 2019), vol. 144 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, pp. 63:1\u201363:13 (2019)"},{"issue":"4","key":"4_CR13","first-page":"1419","volume":"33","author":"M J\u00fcnger","year":"2021","unstructured":"J\u00fcnger, M., Mallach, S.: Exact facetial odd-cycle separation for maximum cut and binary quadratic optimization. INFORMS J. Comput. 33(4), 1419\u20131430 (2021)","journal-title":"INFORMS J. Comput."},{"key":"4_CR14","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, New York, The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"4_CR15","unstructured":"Liers, F.: Contributions to determining exact ground-states of Ising spin-glasses and to their physics. PhD thesis, Universit\u00e4t zu K\u00f6ln (2004)"},{"issue":"4","key":"4_CR16","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1007\/s11590-020-01667-z","volume":"15","author":"VH Nguyen","year":"2021","unstructured":"Nguyen, V.H., Minoux, M.: Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results. Optim. Lett. 15(4), 1041\u20131060 (2021)","journal-title":"Optim. Lett."},{"issue":"1","key":"4_CR17","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M Padberg","year":"1989","unstructured":"Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45(1), 139\u2013172 (1989)","journal-title":"Math. Program."},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s12532-023-00236-6","volume":"15","author":"D Rehfeldt","year":"2023","unstructured":"Rehfeldt, D., Koch, T., Shinano, Y.: Faster exact solution of sparse maxCut and QUBO problems. Math. Program. Comput. 15, 445\u2013470 (2023)","journal-title":"Math. Program. Comput."},{"issue":"10","key":"4_CR19","doi-asserted-by":"publisher","first-page":"6581","DOI":"10.1109\/TIT.2012.2204955","volume":"58","author":"X Zhang","year":"2012","unstructured":"Zhang, X., Siegel, P.H.: Adaptive cut generation algorithm for improved linear programming decoding of binary linear codes. IEEE Trans. Inf. Theory 58(10), 6581\u20136594 (2012)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-60924-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T03:38:46Z","timestamp":1716349126000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-60924-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031609237","9783031609244"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-60924-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ISCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"La Laguna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 May 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"isco2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}