{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:54:06Z","timestamp":1771329246082,"version":"3.50.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319455860","type":"print"},{"value":"9783319455877","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-45587-7_18","type":"book-chapter","created":{"date-parts":[[2016,9,9]],"date-time":"2016-09-09T00:01:21Z","timestamp":1473379281000},"page":"201-212","source":"Crossref","is-referenced-by-count":2,"title":["Strengthening Chv\u00e1tal-Gomory Cuts for the Stable Set Problem"],"prefix":"10.1007","author":[{"given":"Adam N.","family":"Letchford","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesca","family":"Marzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Rossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Smriglio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,10]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s10107-008-0243-8","volume":"122","author":"K Andersen","year":"2010","unstructured":"Andersen, K., Pochet, Y.: Coefficient strengthening: a tool for reformulating mixed-integer programs. Math. Program. 122, 121\u2013154 (2010)","journal-title":"Math. Program."},{"key":"18_CR2","unstructured":"Bornd\u00f6rfer, R.: Aspects of Set Packing, Partitioning and Covering. Doctoral thesis, Technical University of Berlin (1998)"},{"key":"18_CR3","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.) Cliques, Coloring and Satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 11\u201328 (1996)","DOI":"10.1090\/dimacs\/026\/02"},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/s10107-010-0363-9","volume":"124","author":"IM Bomze","year":"2010","unstructured":"Bomze, I.M., Frommlet, F., Locatelli, M.: Copositivity cuts for improving SDP bounds on the clique number. Math. Program. 124, 13\u201332 (2010)","journal-title":"Math. Program."},{"key":"18_CR5","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. Optim. 16, 726\u2013750 (2006)","journal-title":"SIAM J. Optim."},{"key":"18_CR6","unstructured":"DIMACS repository. ftp:\/\/dimacs.rutgers.edu\/pub\/challenge\/graph\/benchmarks\/clique"},{"key":"18_CR7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discr. Math. 4, 305\u2013337 (1973)","journal-title":"Discr. Math."},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Corr\u00eaa, R.C., Delle Donne, D., Koch, I., Marenco, J.: General cut-generating procedures for the stable set polytope (2015). arXiv:1512.08757v1","DOI":"10.1016\/j.endm.2015.07.044"},{"key":"18_CR9","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/j.endm.2015.07.044","volume":"50","author":"RC Corr\u00eaa","year":"2015","unstructured":"Corr\u00eaa, R.C., Delle Donne, D., Koch, I., Marenco, J.: A strengthened general cut-generating procedure for the stable set polytope. Elec. Notes Discr. Math. 50, 261\u2013266 (2015)","journal-title":"Elec. Notes Discr. Math."},{"key":"18_CR10","unstructured":"Coniglio, S., Gualandi, S.: On the exact separation of rank inequalities for the maximum stable set problem. Optimization (2014). http:\/\/www.optimization-online.org\/DB_HTML\/2014\/08\/4514.html"},{"key":"18_CR11","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":"18_CR12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-006-0054-8","volume":"110","author":"M Fischetti","year":"2007","unstructured":"Fischetti, M., Lodi, A.: Optimizing over the first Chv\u00e1tal closure. Math. Program. 110, 3\u201320 (2007)","journal-title":"Math. Program."},{"key":"18_CR13","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s10107-012-0513-3","volume":"141","author":"M Giandomenico","year":"2013","unstructured":"Giandomenico, M., Rossi, F., Smriglio, S.: Strong lift-and-project cutting planes for the stable set problem. Math. Program. 141, 165\u2013192 (2013)","journal-title":"Math. Program."},{"key":"18_CR14","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s10107-008-0219-8","volume":"120","author":"M Giandomenico","year":"2009","unstructured":"Giandomenico, M., Letchford, A., Rossi, F., Smriglio, S.: An application of the Lov\u00e1sz-Schrijver $$M(K, K)$$ operator to the stable set problem. Math. Program. 120, 381\u2013401 (2009)","journal-title":"Math. Program."},{"key":"18_CR15","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.endm.2013.05.088","volume":"41","author":"M Giandomenico","year":"2013","unstructured":"Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S.: Approximating the Lov\u00e1sz theta function with the subgradient method. Elec. Notes Discr. Math. 41, 157\u2013164 (2013)","journal-title":"Elec. Notes Discr. Math."},{"issue":"3","key":"18_CR16","doi-asserted-by":"crossref","first-page":"1944","DOI":"10.1137\/140966332","volume":"25","author":"M Giandomenico","year":"2015","unstructured":"Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S.: Ellipsoidal relaxations of the stable set problem: theory and algorithms. SIAM J. Optim. 25(3), 1944\u20131963 (2015)","journal-title":"SIAM J. Optim."},{"key":"18_CR17","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"RE Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64, 275\u2013278 (1958)","journal-title":"Bull. Amer. Math. Soc."},{"key":"18_CR18","first-page":"269","volume-title":"Recent Advances in Mathematical Programming","author":"RE Gomory","year":"1963","unstructured":"Gomory, R.E.: An algorithm for integer solutions to linear programs. In: Graves, R.L., Wolfe, P. (eds.) Recent Advances in Mathematical Programming, pp. 269\u2013302. McGraw-Hill, New York (1963)"},{"key":"18_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms in Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.J.: Geometric Algorithms in Combinatorial Optimization. Wiley, New York (1988)"},{"key":"18_CR20","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. Optim. 13, 1014\u20131028 (2003)","journal-title":"SIAM J. Optim."},{"key":"18_CR21","volume-title":"Cliques, Coloring, Satisfiability: Observation of Strains: The 2nd DIMACS Implementation Challenge","year":"2011","unstructured":"Johnson, D.S., Trick, M.A. (eds.): Cliques, Coloring, Satisfiability: Observation of Strains: The 2nd DIMACS Implementation Challenge. American Mathematical Society, Providence (2011)"},{"key":"18_CR22","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-\\epsilon }$$ . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"18_CR23","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1111\/j.1475-3995.2009.00744.x","volume":"17","author":"E Holm","year":"2010","unstructured":"Holm, E., Torres, L.M., Wagler, A.K.: On the Chv\u00e1tal rank of linear relaxations of the stable set polytope. Int. Trans. Oper. Res. 17, 827\u2013849 (2010)","journal-title":"Int. Trans. Oper. Res."},{"key":"18_CR24","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/s10107-014-0771-3","volume":"150","author":"M Locatelli","year":"2015","unstructured":"Locatelli, M.: Improving upper bounds for the clique number by non-valid inequalities. Math. Prog. 150, 511\u2013525 (2015)","journal-title":"Math. Prog."},{"key":"18_CR25","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. Inform. Theor. 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Theor."},{"key":"18_CR26","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. Optim. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"18_CR27","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1057\/jors.1992.71","volume":"43","author":"GL Nemhauser","year":"1992","unstructured":"Nemhauser, G.L., Sigismondi, G.: A strong cutting plane\/branch-and-bound algorithm for node packing. J. Oper. Res. Soc. 43, 443\u2013457 (1992)","journal-title":"J. Oper. Res. Soc."},{"key":"18_CR28","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"MW 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":"18_CR29","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/s10878-009-9264-3","volume":"21","author":"S Rebennack","year":"2011","unstructured":"Rebennack, S., Oswald, M., Theis, D.O., Seitz, H., Reinelt, G., Pardalos, P.M.: A branch and cut solver for the maximum stable set problem. J. Comb. Opt. 21, 434\u2013457 (2011)","journal-title":"J. Comb. Opt."},{"key":"18_CR30","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."},{"issue":"2","key":"18_CR31","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 $$\\theta $$ function for random graphs. Combinatorica. 2(2), 153\u2013155 (1982)","journal-title":"Combinatorica."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-45587-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T04:48:44Z","timestamp":1568350124000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-45587-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319455860","9783319455877"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-45587-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}