{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:53:51Z","timestamp":1771329231470,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,4,11]],"date-time":"2008-04-11T00:00:00Z","timestamp":1207872000000},"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":[[2009,9]]},"DOI":"10.1007\/s10107-008-0219-8","type":"journal-article","created":{"date-parts":[[2008,4,10]],"date-time":"2008-04-10T13:26:03Z","timestamp":1207833963000},"page":"381-401","source":"Crossref","is-referenced-by-count":16,"title":["An application of the Lov\u00e1sz\u2013Schrijver M(K, K) operator to the stable set problem"],"prefix":"10.1007","volume":"120","author":[{"given":"Monia","family":"Giandomenico","sequence":"first","affiliation":[]},{"given":"Adam N.","family":"Letchford","sequence":"additional","affiliation":[]},{"given":"Fabrizio","family":"Rossi","sequence":"additional","affiliation":[]},{"given":"Stefano","family":"Smriglio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,4,11]]},"reference":[{"key":"219_CR1","doi-asserted-by":"crossref","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G., Pataki G.: Polyhedral methods for the maximum clique problem. In: Johnson, D.S., Trick, M.A. (eds.) Op. cit., pp. 11\u201328. (1996)","DOI":"10.1090\/dimacs\/026\/02"},{"key":"219_CR2","unstructured":"Bornd\u00f6rfer, R.: Aspects of Set Packing, Partitioning and Covering. Doctoral Thesis, Technical University of Berlin (1998)"},{"key":"219_CR3","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1137\/040609574","volume":"16","author":"S. Burer","year":"2006","unstructured":"Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Opt. 16, 726\u2013750 (2006)","journal-title":"SIAM J. Opt."},{"key":"219_CR4","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s101070100267","volume":"92","author":"E. Cheng","year":"2002","unstructured":"Cheng, E., De Vries, S.: Antiweb-wheel inequalities and their separation problems over the stable set polytopes. Math. Program. 92, 153\u2013175 (2002)","journal-title":"Math. Program."},{"key":"219_CR5","unstructured":"Repository ftp:\/\/dimacs.rutgers.edu\/pub\/challenge\/graph\/benchmarks\/clique"},{"key":"219_CR6","unstructured":"Website http:\/\/www.math.uni-klu.ac.at\/or\/Software\/software.html"},{"key":"219_CR7","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s10107-006-0026-z","volume":"109","author":"I. Dukanovic","year":"2007","unstructured":"Dukanovic, I., Rendl, F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Math. Program. 109, 345\u2013365 (2007)","journal-title":"Math. Program."},{"key":"219_CR8","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0095-8956(72)90032-9","volume":"12","author":"D.R. Fulkerson","year":"1972","unstructured":"Fulkerson, D.R.: Anti-blocking polyhedra. J. Comb. Th. (B) 12, 50\u201371 (1972)","journal-title":"J. Comb. Th. (B)"},{"key":"219_CR9","unstructured":"Giandomenico, M.: Extended Formulations for the Stable Set Problem: Theory and Experiments. Phd Thesis, University of Rome \u2018La Sapienza\u2019 (2006)"},{"key":"219_CR10","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579262","volume":"6","author":"A.M.H. Gerards","year":"1986","unstructured":"Gerards, A.M.H., Schrijver, A.J.: Matrices with the Edmonds\u2013Johnson property. Combinatorica 6, 365\u2013379 (1986)","journal-title":"Combinatorica"},{"key":"219_CR11","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10107-005-0604-5","volume":"106","author":"M. Giandomenico","year":"2006","unstructured":"Giandomenico, M., Letchford, A.N.: Exploring the relationship between max-cut and stable set relaxations. Math. Program. 106, 159\u2013175 (2006)","journal-title":"Math. Program."},{"key":"219_CR12","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":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.J.: Geometric Algorithms and Combinatorial Optimization. Wiley, New York (1988)"},{"key":"219_CR13","doi-asserted-by":"crossref","first-page":"1014","DOI":"10.1137\/S1052623401394092","volume":"13","author":"G. Gruber","year":"2003","unstructured":"Gruber, G., Rendl, F.: Computational experience with stable set relaxations. SIAM J. Opt. 13, 1014\u20131028 (2003)","journal-title":"SIAM J. Opt."},{"key":"219_CR14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1-\u03f5. Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"219_CR15","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1287\/mnsc.39.6.657","volume":"39","author":"K. Hoffman","year":"1993","unstructured":"Hoffman, K., Padberg, M.W.: Solving airline crew scheduling problems by branch-and-cut. Manage. Sci. 39, 657\u2013682 (1993)","journal-title":"Manage. Sci."},{"key":"219_CR16","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Trick, M.A. (eds.) Cliques, Coloring and Satisfiability: the 2nd DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. American Mathematical Society, Providence (1996)","DOI":"10.1090\/dimacs\/026"},{"key":"219_CR17","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF02579314","volume":"2","author":"F. Juh\u00e1sz","year":"1982","unstructured":"Juh\u00e1sz, F.: The asymptotic behaviour of Lov\u00e1sz\u2019 \u03b8 function for random graphs. Combinatorica 2, 153\u2013155 (1982)","journal-title":"Combinatorica"},{"key":"219_CR18","first-page":"225","volume":"77","author":"M. Laurent","year":"1997","unstructured":"Laurent, M., Poljak, S., Rendl, F.: Connections between semidefinite relaxations of the max-cut and stable set problems. Math. Program. 77, 225\u2013246 (1997)","journal-title":"Math. Program."},{"key":"219_CR19","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L. Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: Normal hypergraphs and the perfect graph conjecture. Discr. Math. 2, 253\u2013267 (1972)","journal-title":"Discr. Math."},{"key":"219_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"219_CR21","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.J.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM J. Opt. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Opt."},{"key":"219_CR22","unstructured":"Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. Optimization online, http:\/\/www.optimization-online.org\/DB_FILE\/2007\/10\/1800.pdf (2007)"},{"key":"219_CR23","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1057\/jors.1992.71","volume":"43","author":"G.L. Nemhauser","year":"1992","unstructured":"Nemhauser, G.L., Sigismondi, G.: A strong cutting plane\/branch-and-bound algorithm for node packing. J. Opl. Res. Soc. 43, 443\u2013457 (1992)","journal-title":"J. Opl. Res. Soc."},{"key":"219_CR24","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"M.W. Padberg","year":"1973","unstructured":"Padberg, M.W.: On the facial structure of set packing polyhedra. Math. Program. 5, 199\u2013215 (1973)","journal-title":"Math. Program."},{"key":"219_CR25","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M.W. Padberg","year":"1989","unstructured":"Padberg, M.W.: The boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139\u2013172 (1989)","journal-title":"Math. Program."},{"key":"219_CR26","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/s00607-006-0182-2","volume":"78","author":"J. Povh","year":"2006","unstructured":"Povh, J., Rendl, F., Wiegele, A.: A boundary point method to solve semidefinite programs. Computing 78, 277\u2013286 (2006)","journal-title":"Computing"},{"key":"219_CR27","doi-asserted-by":"crossref","unstructured":"R\u00e9gin, J.-C.: Using constraint programming to solve the maximum clique problem. In: Rossi, F. (ed) Proceedings of CP 2003. Lecture Notes in Computer Science, vol. 2833. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-45193-8_43"},{"key":"219_CR28","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0167-6377(00)00060-2","volume":"28","author":"F. Rossi","year":"2001","unstructured":"Rossi, F., Smriglio, S.: A branch-and-cut algorithm for the maximum cardinality stable set problem. Oper. Res. Lett. 28, 63\u201374 (2001)","journal-title":"Oper. Res. Lett."},{"key":"219_CR29","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"IT-25","author":"A.J. Schrijver","year":"1979","unstructured":"Schrijver, A.J.: A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Inf. Theory IT-25, 425\u2013429 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"219_CR30","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s10898-006-9039-7","volume":"37","author":"E. Tomita","year":"2007","unstructured":"Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique, with computational experiments. J. Glob. Opt. 37, 95\u2013111 (2007)","journal-title":"J. Glob. Opt."},{"key":"219_CR31","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/0012-365X(75)90077-1","volume":"12","author":"L.E. Trotter","year":"1975","unstructured":"Trotter, L.E.: A class of facet-producing graphs for vertex packing polyhedra. Discr. Math. 12, 373\u2013388 (1975)","journal-title":"Discr. Math."},{"key":"219_CR32","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s10589-005-3060-5","volume":"33","author":"E.A. Yildirim","year":"2006","unstructured":"Yildirim, E.A., Fan, X.: On extracting maximum stable sets in perfect graphs using Lov\u00e1sz\u2019s theta function. Comput. Opt. Appl. 33, 229\u2013247 (2006)","journal-title":"Comput. Opt. Appl."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-008-0219-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-008-0219-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-008-0219-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:50:05Z","timestamp":1559123405000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-008-0219-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,11]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["219"],"URL":"https:\/\/doi.org\/10.1007\/s10107-008-0219-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4,11]]}}}