{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:53:52Z","timestamp":1771329232231,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2005,10,18]],"date-time":"2005-10-18T00:00:00Z","timestamp":1129593600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Optim Applic"],"published-print":{"date-parts":[[2006,3]]},"DOI":"10.1007\/s10589-005-3060-5","type":"journal-article","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T13:27:41Z","timestamp":1132752461000},"page":"229-247","source":"Crossref","is-referenced-by-count":13,"title":["On Extracting Maximum Stable Sets in Perfect Graphs Using Lov\u00e1sz's Theta Function"],"prefix":"10.1007","volume":"33","author":[{"given":"E. Alper","family":"Yildirim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofei","family":"Fan-Orzechowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,10,18]]},"reference":[{"key":"3060_CR1","unstructured":"F. Alizadeh, \u201cA sublinear-time randomized parallel algorithm for the maximum clique problem in perfect graphs,\u201d ACM-SIAM Symposium on Discrete Algorithms, vol. 2, pp. 188\u2013194, 1991."},{"issue":"3","key":"3060_CR2","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/BF01581168","volume":"80","author":"N. Alon","year":"1998","unstructured":"N. Alon and N. Kahale, \u201cApproximating the independence number via the theta-function,\u201d Mathematical Programming, vol. 80, no. 3. pp. 253\u2013264, 1998.","journal-title":"Mathematical Programming"},{"issue":"2","key":"3060_CR3","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10107-002-0350-x","volume":"95","author":"H.Y. Benson","year":"2003","unstructured":"H.Y. Benson and R.J. Vanderbei, \u201cSolving problems with semidefinite and related constraints using interior-point methods for nonlinear programming,\u201d Mathematical Programming, vol. 95, no. 2, pp. 279\u2013302, 2003.","journal-title":"Mathematical Programming"},{"key":"3060_CR4","doi-asserted-by":"crossref","unstructured":"S. Benson and Y. Ye, \u201cApproximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation,\u201d in Applications and Algorithms of Complementarity, M. Ferris and J. Pang (Eds.), Kluwer Academic Publishers, 2000, pp. 1\u201318.","DOI":"10.1007\/978-1-4757-3279-5_1"},{"key":"3060_CR5","unstructured":"C. Berge, \u201cF\u00e4rbung von graphen deren s\u00e4mtliche beziehungsweise deren ungerade kreise starr sind (zusammenfassung),\u201d Wissenschaftliche Zeitschrift, Martin Luther Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe, pp. 114\u2013115, 1961."},{"key":"3060_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4757-3023-4_1","volume-title":"Handbook of Combinatorial Optimization (Supplement Volume A)","author":"I.M. Bomze","year":"1999","unstructured":"I.M. Bomze, M. Budinich, P.M. Pardalos, and M. Pelillo, \u201cThe maximum clique problem,\u201d in Handbook of Combinatorial Optimization (Supplement Volume A), D.-Z. Du and P.M. Pardalos (Eds.), Kluwer Academic, Boston, Massachusetts, U.S.A., 1999, pp. 1\u201374."},{"issue":"1","key":"3060_CR7","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s10107-002-0356-4","volume":"94","author":"S. Burer","year":"2002","unstructured":"S. Burer, R.D.C. Monteiro, and Y. Zhang, \u201cMaximum stable set formulations and heuristics based on continuous optimization,\u201d Mathematical Programming, vol. 94, no.1, pp. 137\u2013166, 2002.","journal-title":"Mathematical Programming"},{"issue":"1","key":"3060_CR8","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s101070100279","volume":"93","author":"S. Burer","year":"2002","unstructured":"S. Burer, R.D.C. Monteiro, and Y. Zhang, \u201cSolving a class of semidefinite programs via nonlinear programming,\u201d Mathematical Programming, vol. 93, no. 1, pp. 97\u2013122, 2002.","journal-title":"Mathematical Programming"},{"key":"3060_CR9","unstructured":"M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, and K. Vuskovic, \u201cCleaning for Bergeness,\u201d Technical report, Princeton University, 2003."},{"key":"3060_CR10","unstructured":"M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, \u201cThe strong perfect graph theorem,\u201d Technical report, Princeton University, 2003."},{"key":"3060_CR11","unstructured":"M. Chudnovsky and P. Seymour, \u201cRecognizing Berge graphs,\u201d Technical report, Princeton University, 2003."},{"key":"3060_CR12","unstructured":"G. Cornuejols, X. Liu, and K. Vuskovic, \u201cA polynomial algorithm for recognizing perfect graphs,\u201d Technical report, Carnegie Mellon University, 2003."},{"issue":"1","key":"3060_CR13","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01196133","volume":"17","author":"U. Feige","year":"1997","unstructured":"U. Feige, \u201cRandomized graph products, chromatic numbers, and the Lov\u00e1sz's theta function,\u201d Combinatorica, vol. 17, no. 1, pp. 79\u201390, 1997.","journal-title":"Combinatorica"},{"key":"3060_CR14","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver, \u201cPolynomial algorithms for perfect graphs,\u201d Annals of Discrete Mathematics, pp. 325\u2013356, 1984.","DOI":"10.1016\/S0304-0208(08)72943-8"},{"key":"3060_CR15","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, Springer, New York, 1988."},{"issue":"4","key":"3060_CR16","doi-asserted-by":"crossref","first-page":"1014","DOI":"10.1137\/S1052623401394092","volume":"13","author":"G. Gruber","year":"2003","unstructured":"G. Gruber and F. Rendl, \u201cComputational experience with stable set relaxations,\u201d SIAM Journal on Optimization, vol. 13 no. 4, pp. 1014\u20131028, 2003.","journal-title":"SIAM Journal on Optimization"},{"key":"3060_CR17","doi-asserted-by":"crossref","unstructured":"J. Hastad, \u201cClique is hard to approximate within $$n^{1-\\epsilon}$$ ,\u201d Acta Mathematica, vol. 182, no. 1, pp. 105\u2013142, 1999.","DOI":"10.1007\/BF02392825"},{"issue":"3","key":"3060_CR18","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C. Helmberg","year":"2000","unstructured":"C. Helmberg and F. Rendl, \u201cA spectral bundle method for semidefinite programming,\u201d SIAM Journal on Optimization, vol. 10, no. 3, pp. 673\u2013696, 2000.","journal-title":"SIAM Journal on Optimization"},{"key":"3060_CR19","unstructured":"S. Hougardy, \u201cInclusions between classes of perfect graphs,\u201d Technical report, Humboldt-Universit\u00e4t zu Berlin, 1998. Available at http:\/\/www.informatik.hu-berlin.de\/~hougardy\/paper\/classes.html."},{"key":"3060_CR20","doi-asserted-by":"crossref","unstructured":"D.E. Knuth, \u201cThe sandwich theorem,\u201d Electronic Journal of Combinatorics, vol. 1, no. 1, A1, pp. 1\u201348, 1994.","DOI":"10.37236\/1193"},{"key":"3060_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, \u201cOn the Shannon capacity of a graph,\u201d IEEE Transactions on Information Theory, vol. 25, pp. 1\u20137, 1979.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"3060_CR22","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"L. Lov\u00e1sz and A. Schrijver, \u201cCones of matrices and set-functions and 0-1 optimization,\u201d SIAM Journal on Optimization, vol. 1, no. 2, pp. 166\u2013190, 1991.","journal-title":"SIAM Journal on Optimization"},{"key":"3060_CR23","doi-asserted-by":"crossref","unstructured":"J. Mycielski, \u201cSur le coloriage des graphes,\u201d Colloq. Math., vol. 3, 1955.","DOI":"10.4064\/cm-3-2-161-162"},{"issue":"1","key":"3060_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T. Stephen","year":"1999","unstructured":"T. Stephen and L. Tun\u00e7el, \u201cOn a representation of the matching polytope via semidefinite liftings,\u201d Mathematics of Operations Research, vol. 24 no. 1, pp. 1\u20137, 1999.","journal-title":"Mathematics of Operations Research"},{"key":"3060_CR25","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"R.H. T\u00fct\u00fcnc\u00fc","year":"2003","unstructured":"R.H. T\u00fct\u00fcnc\u00fc, K.C. Toh, and M.J. Todd, \u201cSolving semidefinite-quadratic-linear programs using SDPT3,\u201d Mathematical Programming, vol. 95, pp. 189\u2013217, 2003.","journal-title":"Mathematical Programming"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-005-3060-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-005-3060-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-005-3060-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T05:07:08Z","timestamp":1586581628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-005-3060-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10,18]]},"references-count":25,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["3060"],"URL":"https:\/\/doi.org\/10.1007\/s10589-005-3060-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10,18]]}}}