{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T05:24:57Z","timestamp":1772515497326,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,1,11]],"date-time":"2021-01-11T00:00:00Z","timestamp":1610323200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,11]],"date-time":"2021-01-11T00:00:00Z","timestamp":1610323200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s10107-020-01600-3","type":"journal-article","created":{"date-parts":[[2021,1,11]],"date-time":"2021-01-11T16:24:36Z","timestamp":1610382276000},"page":"387-407","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Persistency of linear programming relaxations for the stable set problem"],"prefix":"10.1007","volume":"192","author":[{"given":"Elisabeth","family":"Rodr\u00edguez-Heck","sequence":"first","affiliation":[]},{"given":"Karl","family":"Stickler","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6615-5983","authenticated-orcid":false,"given":"Matthias","family":"Walter","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Weltge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,11]]},"reference":[{"issue":"2","key":"1600_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1016\/j.disopt.2007.02.001","volume":"5","author":"E Boros","year":"2008","unstructured":"Boros, E., Hammer, P.L., Sun, R., Tavares, G.: A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discrete Optim. 5(2), 501\u2013529 (2008). In Memory of George B. Dantzig","journal-title":"Discrete Optim."},{"issue":"2","key":"1600_CR2","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/0095-8956(75)90041-6","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: On certain polytopes associated with graphs. J. Comb. Theory Ser. B 18(2), 138\u2013154 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"7","key":"1600_CR3","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1109\/TPAMI.2014.2382109","volume":"37","author":"A Fix","year":"2015","unstructured":"Fix, A., Gruber, A., Boros, E., Zabih, R.: A hypergraph-based reduction for higher-order binary Markov random fields. IEEE Trans. Pattern Anal. Mach. Intell. 37(7), 1387\u20131395 (2015)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"2","key":"1600_CR4","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0095-8956(86)90076-6","volume":"40","author":"GR Grimmett","year":"1986","unstructured":"Grimmett, G.R.: An exact threshold theorem for random graphs and the node-packing problem. J. Comb. Theory Ser. B 40(2), 187\u2013195 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"1600_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0167-6377(85)90024-0","volume":"4","author":"GR Grimmett","year":"1985","unstructured":"Grimmett, G.R., Pulleyblank, W.R.: Random near-regular graphs and the node packing problem. Oper. Res. Lett. 4(4), 169\u2013174 (1985)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"1600_CR6","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1137\/0603052","volume":"3","author":"PL Hammer","year":"1982","unstructured":"Hammer, P.L., Hansen, P., Simeone, B.: Vertices belonging to all or to no maximum stable sets of a graph. SIAM J. Algebraic Discrete Methods 3(4), 511\u2013522 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"2","key":"1600_CR7","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF02612354","volume":"28","author":"PL Hammer","year":"1984","unstructured":"Hammer, P.L., Hansen, P., Simeone, B.: Roof duality, complementation and persistency in quadratic 0\u20131 optimization. Math. Programm. 28(2), 121\u2013155 (1984)","journal-title":"Math. Programm."},{"issue":"6","key":"1600_CR8","doi-asserted-by":"publisher","first-page":"1234","DOI":"10.1109\/TPAMI.2010.91","volume":"33","author":"H Ishikawa","year":"2011","unstructured":"Ishikawa, H.: Transformation of general binary MRF minimization to the first-order case. IEEE Trans. Pattern Anal. Mach. Intell. 33(6), 1234\u20131249 (2011)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"4","key":"1600_CR9","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1137\/0211053","volume":"11","author":"RM Karp","year":"1982","unstructured":"Karp, R.M., Papadimitriou, C.H.: On linear characterizations of combinatorial optimization problems. SIAM J. Comput. 11(4), 620\u2013632 (1982)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"1600_CR10","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1109\/TPAMI.2007.1031","volume":"29","author":"V Kolmogorov","year":"2007","unstructured":"Kolmogorov, V., Rother, C.: Minimizing nonsubmodular functions with graph cuts\u2014a review. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1274\u20131279 (2007)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"1600_CR11","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Programm. 8(1), 232\u2013248 (1975)","journal-title":"Math. Programm."},{"issue":"1","key":"1600_CR12","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0166-218X(03)00400-1","volume":"132","author":"G Oriolo","year":"2003","unstructured":"Oriolo, G.: Clique family inequalities for the stable set polytope of quasi-line graphs. Discrete Appl. Math. 132(1), 185\u2013201 (2003). Stability in Graphs and Related Topics","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1600_CR13","doi-asserted-by":"publisher","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. Programm. 5(1), 199\u2013215 (1973)","journal-title":"Math. Programm."},{"issue":"1","key":"1600_CR14","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01593772","volume":"12","author":"J-C Picard","year":"1977","unstructured":"Picard, J.-C., Queyranne, M.: On the integer-valued variables in the linear vertex packing problem. Math. Programm. 12(1), 97\u2013101 (1977)","journal-title":"Math. Programm."},{"issue":"1","key":"1600_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF01588228","volume":"17","author":"WR Pulleyblank","year":"1979","unstructured":"Pulleyblank, W.R.: Minimum node covers and 2-bicritical graphs. Math. Programm. 17(1), 91\u2013103 (1979)","journal-title":"Math. Programm."},{"key":"1600_CR16","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"key":"1600_CR17","unstructured":"Sewell, E.C.: Stability critical graphs and the stable set polytope. Technical report, Cornell University Operations Research and Industrial Engineering, (1990)"},{"issue":"4","key":"1600_CR18","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/0012-365X(75)90077-1","volume":"12","author":"LE Trotter","year":"1975","unstructured":"Trotter, L.E.: A class of facet producing graphs for vertex packing polyhedra. Discrete Math. 12(4), 373\u2013388 (1975)","journal-title":"Discrete Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01600-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01600-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01600-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T17:18:16Z","timestamp":1646846296000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01600-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,11]]},"references-count":18,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1600"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01600-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,11]]},"assertion":[{"value":"22 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}