{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T17:33:43Z","timestamp":1778348023471,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1993,2,1]],"date-time":"1993-02-01T00:00:00Z","timestamp":728524800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1993,2]]},"DOI":"10.1007\/bf01585184","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T09:16:57Z","timestamp":1114679817000},"page":"557-574","source":"Crossref","is-referenced-by-count":123,"title":["Laplacian eigenvalues and the maximum cut problem"],"prefix":"10.1007","volume":"62","author":[{"given":"C.","family":"Delorme","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Poljak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","series-title":"Rapport de Recherche","volume-title":"On the complexity of max-cut","author":"F. Barahona","year":"1980","unstructured":"F. Barahona, \u201cOn the complexity of max-cut,\u201d Rapport de Recherche 186, Math\u00e9matiques appliqu\u00e9es et Informatique, Universit\u00e9 Scientifique et m\u00e9dicale de Grenoble (Grenoble, France, 1980)."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0167-6377(83)90031-7","volume":"2","author":"F. Barahona","year":"1983","unstructured":"F. Barahona, \u201cOn some weakly bipartite graphs,\u201dOperations Research Letters 2 (1983) 239\u2013242.","journal-title":"Operations Research Letters"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1988","unstructured":"F. Barahona, M. Gr\u00f6tschel, M. J\u00fcnger and G. Reinelt, \u201cAn application of combinatorial optimization to statistical physics and circuit layout design,\u201dOperations Research 36 (1988) 493\u2013513.","journal-title":"Operations Research"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01587084","volume":"44","author":"F. Barahona","year":"1989","unstructured":"F. Barahona, M. J\u00fcnger and G. Reinelt, \u201cExperiments in quadratic 0\u20131 programming,\u201dMathematical Programming 44 (1989) 127\u2013137.","journal-title":"Mathematical Programming"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1137\/0606048","volume":"6","author":"E.R. Barnes","year":"1985","unstructured":"E.R. Barnes and A.J. Hoffman, \u201cOn transportation problems with upper bounds on leading rectangles,\u201dSIAM Journal on Algebraic Discrete Methods 6 (1985) 487\u2013496.","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"CR6","unstructured":"R. Boppana, \u201cEigenvalues and graph bisection: an average case analysis,\u201d in:FOCS (1987) pp. 280\u2013285."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0012-365X(93)90151-I","volume":"111","author":"C. Delorme","year":"1993","unstructured":"C. Delorme and S. Poljak, \u201cThe performance of an eigenvalue bound on the max-cut problem in some classes of graphs,\u201dDiscrete Mathematics 111 (1993) 145\u2013156.","journal-title":"Discrete Mathematics"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1006\/eujc.1993.1035","volume":"14","author":"C. Delorme","year":"1993","unstructured":"C. Delorme and S. Poljak, \u201cCombinatorial properties and the complexity of a max-cut approximation,\u201dEuropean Journal of Combinatorics 14 (1993) 313\u2013333.","journal-title":"European Journal of Combinatorics"},{"key":"CR9","volume-title":"Introduction to Minimax","author":"V.F. Dem'ianov","year":"1974","unstructured":"V.F. Dem'ianov and V.N. Malozev,Introduction to Minimax (Wiley, New York, 1974)."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1147\/rd.175.0420","volume":"17","author":"W.E. Donath","year":"1973","unstructured":"W.E. Donath and A.J. Hofmann, \u201cLower bounds for the partitioning of graphs,\u201dIBM Journal on Research and Development 17 (1973) 420\u2013425.","journal-title":"IBM Journal on Research and Development"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M. Fiedler","year":"1973","unstructured":"M. Fiedler, \u201cAlgebraic connectivity of graphs,\u201dCzechoslovak Mathematical Journal 23 (1973) 298\u2013305.","journal-title":"Czechoslovak Mathematical Journal"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0012-365X(92)90133-Z","volume":"105","author":"J. Fonlupt","year":"1992","unstructured":"J. Fonlupt, A.R. Mahjoub and J.P. Uhry, \u201cCompositions in the bipartite subgraph polytope,\u201dDiscrete Mathematics 105 (1992) 73\u201391.","journal-title":"Discrete Mathematics"},{"key":"CR13","volume-title":"Computers and Intractability: A guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson,Computers and Intractability: A guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979)."},{"key":"CR14","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver,Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics No. 2 (Springer, Berlin, 1988)."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0167-6377(81)90020-1","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel and W.R. Pulleyblank, \u201cWeakly bipartite graphs and the max-cut problem,\u201dOperations Research Letters 1 (1981) 23\u201327.","journal-title":"Operations Research Letters"},{"key":"CR16","series-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai","first-page":"313","volume-title":"Algebraic Methods in Graph Theory","author":"F. Juh\u00e1sz","year":"1982","unstructured":"F. Juh\u00e1sz, \u201cOn the spectrum of a random graph,\u201d in: L. Lov\u00e1sz and V.T. S\u00f3s, eds.,Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis J\u00e1nos Bolyai No. 25 (North-Holland, Amsterdam, 1982) pp. 313\u2013316."},{"key":"CR17","volume-title":"Theory of Matrices","author":"P. Lancaster","year":"1969","unstructured":"P. Lancaster,Theory of Matrices (Academic Press, New York, 1969)."},{"issue":"115","key":"CR18","doi-asserted-by":"crossref","first-page":"343","DOI":"10.21136\/CMJ.1990.102386","volume":"40","author":"B. Mohar","year":"1990","unstructured":"B. Mohar and S. Poljak, \u201cEigenvalues and the max-cut problem,\u201dCzechoslovak Mathematical Journal 40(115) (1990) 343\u2013352.","journal-title":"Czechoslovak Mathematical Journal"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1137\/0609021","volume":"9","author":"M.L. Overton","year":"1988","unstructured":"M.L. Overton, \u201cOn minimizing the maximum eigenvalue of a symmetric matrix,\u201dSIAM Journal on Matrix Analysis and Applications 9 (1988) 256\u2013268.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"CR20","series-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai","volume-title":"Sets, Graphs and Numbers","author":"S. Poljak","year":"1991","unstructured":"S. Poljak, \u201cPolyhedral and eigenvalue approximations of the max-cut problem,\u201d to appear in:Sets, Graphs and Numbers, Colloquia Mathematica Societatis J\u00e1nos Bolyai No. 59 (North-Holland, Amsterdam, 1991)."},{"key":"CR21","volume-title":"\u201cSolving the max-cut problem using eigenvalues,\u201d Technical Report 91735-OR","author":"S. Poljak","year":"1991","unstructured":"S. Poljak and F. Rendl, \u201cSolving the max-cut problem using eigenvalues,\u201d Technical Report 91735-OR, Institut f\u00fcr Diskrete Mathematik, Universit\u00e4t Bonn (Bonn, 1991)."},{"key":"CR22","volume-title":"\u201cThe expected relative error of the polyhedral approximation of the max-cut problem,\u201d Technical Report 92757","author":"S. Poljak","year":"1992","unstructured":"S. Poljak and Zs. Tuza, \u201cThe expected relative error of the polyhedral approximation of the max-cut problem,\u201d Technical Report 92757, Institut f\u00fcr Diskrete Mathematik, Universit\u00e4t Bonn (Bonn, 1992)."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585184.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585184\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,10]],"date-time":"2021-07-10T02:58:33Z","timestamp":1625885913000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,2]]},"references-count":22,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1993,2]]}},"alternative-id":["BF01585184"],"URL":"https:\/\/doi.org\/10.1007\/bf01585184","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,2]]}}}