{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T23:28:43Z","timestamp":1750116523269,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T00:00:00Z","timestamp":1588032000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T00:00:00Z","timestamp":1588032000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["PZ00P2_154779"],"award-info":[{"award-number":["PZ00P2_154779"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10107-020-01502-4","type":"journal-article","created":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T16:33:15Z","timestamp":1588091595000},"page":"53-84","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Separation routine and extended formulations for the stable set problem in claw-free graphs"],"prefix":"10.1007","volume":"188","author":[{"given":"Yuri","family":"Faenza","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianpaolo","family":"Oriolo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gautier","family":"Stauffer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,28]]},"reference":[{"key":"1502_CR1","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1137\/0606047","volume":"6","author":"E Balas","year":"1985","unstructured":"Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. SIAM J. Algebr. Discrete Methods 6, 466\u2013486 (1985)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"1502_CR2","doi-asserted-by":"crossref","unstructured":"Bonomo, F., Oriolo, G., Snels, C.: Minimum weighted clique cover on strip-composed perfect graphs. In: WG 2012, pp. 22\u201333 (2012)","DOI":"10.1007\/978-3-642-34611-8_6"},{"key":"1502_CR3","first-page":"153","volume":"327","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Seymour, P.: The structure of claw-free graphs. Surv. Comb. 327, 153\u2013171 (2005)","journal-title":"Surv. Comb."},{"key":"1502_CR4","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1016\/j.jctb.2008.03.002","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.: Claw free graphs IV. Global structure. J. Comb. Theory Ser. B 98, 1373\u20131410 (2008)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1502_CR5","doi-asserted-by":"publisher","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. Discrete Math. 4, 305\u2013337 (1973)","journal-title":"Discrete Math."},{"key":"1502_CR6","volume-title":"Combinatorial Optimization","author":"WJ Cook","year":"1998","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)"},{"key":"1502_CR7","unstructured":"Dubois, A., Rouire, M.: Algorithmes de d\u00e9composition dans les graphes sans griffe et couplage: Travail d\u2019\u00c9tude et de Recherche. Master MIMSE, Universit\u00e9 de Bordeaux (2011)"},{"key":"1502_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. 69, 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bur. Stand."},{"issue":"1","key":"1502_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00493-008-2244-x","volume":"28","author":"F Eisenbrand","year":"2008","unstructured":"Eisenbrand, F., Oriolo, G., Stauffer, G., Ventura, P.: Circular one matrices and the stable set polytope of quasi-line graphs. Combinatorica 28(1), 45\u201367 (2008)","journal-title":"Combinatorica"},{"key":"1502_CR10","unstructured":"Faenza, Y.: On the interplay between extended formulations and algorithms in some combinatorial problems. Ph.D. thesis, Sapienza university of Rome (2010)"},{"key":"1502_CR11","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: An algorithmic decomposition of claw-free graphs leading to an $$O(n^3)$$-algorithm for the weighted stable set problem. In: Proceedings of SODA 2011, pp. 630\u2013646 (2011)","DOI":"10.1137\/1.9781611973082.49"},{"key":"1502_CR12","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: Separating stable sets in claw-free graphs via Padberg\u2013Rao and compact linear programs. In: Proceedings of SODA 2012, pp. 1298\u20131308 (2012)","DOI":"10.1137\/1.9781611973099.102"},{"issue":"4","key":"1502_CR13","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/2629600","volume":"61","author":"Y Faenza","year":"2014","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: Solving the maximum weighted stable set problem in claw-free graphs via decomposition. J. ACM 61(4), 20\u201341 (2014)","journal-title":"J. ACM"},{"issue":"2","key":"1502_CR14","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/2716307","volume":"62","author":"S Fiorini","year":"2015","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2), 17:1\u201317:23 (2015)","journal-title":"J. ACM"},{"issue":"4","key":"1502_CR15","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.orl.2008.01.003","volume":"36","author":"A Galluccio","year":"2008","unstructured":"Galluccio, A., Gentile, C., Ventura, P.: Gear composition and the stable set polytope. Oper. Res. Lett. 36(4), 419\u2013423 (2008)","journal-title":"Oper. Res. Lett."},{"key":"1502_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2014.02.009","volume":"108","author":"A Galluccio","year":"2014","unstructured":"Galluccio, A., Gentile, C., Ventura, P.: The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are-perfect. J. Comb. Theory Ser. B 108, 1\u201328 (2014)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1502_CR17","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.jctb.2014.02.006","volume":"107","author":"A Galluccio","year":"2014","unstructured":"Galluccio, A., Gentile, C., Ventura, P.: The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are-perfect. J. Comb. Theory Ser. B 107, 92\u2013122 (2014)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1502_CR18","doi-asserted-by":"publisher","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., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988)"},{"key":"1502_CR19","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02239975","volume":"39","author":"M Gr\u00f6tschel","year":"1987","unstructured":"Gr\u00f6tschel, M., Holland, O.: A cutting-plane algorithm for minimum perfect 2-matching. Computing 39, 327\u2013344 (1987)","journal-title":"Computing"},{"issue":"2","key":"1502_CR20","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1016\/j.ejor.2016.12.047","volume":"260","author":"M Hopf","year":"2017","unstructured":"Hopf, M., Thielen, C., Wendt, O.: Competitive algorithms for multistage online scheduling. Eur. J. Oper. Res. 260(2), 468\u2013481 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"1502_CR21","first-page":"2","volume":"85","author":"V Kaibel","year":"2011","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85, 2\u20137 (2011)","journal-title":"Optima"},{"key":"1502_CR22","doi-asserted-by":"crossref","unstructured":"Kaibel, V., Loos, A.: Branched polyhedral systems. In: Eisenbrand, F., Shepherd, B. (eds.) Proceedings of IPCO XIV, pp. 177\u2013190 (2010)","DOI":"10.1007\/978-3-642-13036-6_14"},{"key":"1502_CR23","doi-asserted-by":"crossref","unstructured":"Kose, A., Medard, M.: Scheduling wireless ad hoc networks in polynomial time using claw-free conflict graphs. (2017). arXiv:1711.01620","DOI":"10.1109\/PIMRC.2017.8292404"},{"issue":"3","key":"1502_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"RK Martin","year":"1991","unstructured":"Martin, R.K.: Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3), 119\u2013128 (1991)","journal-title":"Oper. Res. Lett."},{"key":"1502_CR25","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory 28, 284\u2013304 (1980)","journal-title":"J. Comb. Theory"},{"issue":"2","key":"1502_CR26","first-page":"194","volume":"44","author":"D Nakamura","year":"2001","unstructured":"Nakamura, D., Tamura, A.: A revision of Minty\u2019s algorithm for finding a maximum weighted stable set of a claw-free graph. J. Oper. Res. Soc. Jpn. 44(2), 194\u20132004 (2001)","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"1502_CR27","unstructured":"Nobili, P., Sassano A.: An $${\\cal{O}}(n^2 \\log (n))$$ algorithm for the weighted stable set problem in claw-free graphs. (2015). arXiv:1501.05775"},{"key":"1502_CR28","doi-asserted-by":"crossref","unstructured":"Oriolo, G., Pietropaoli, U., Stauffer, G.: A new algorithm for the maximum weighted stable set problem in claw-free graphs. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) Proceedings Thirteenth IPCO Conference, pp. 77\u201396 (2008)","DOI":"10.1007\/978-3-540-68891-4_6"},{"key":"1502_CR29","first-page":"8","volume":"86","author":"MW Padberg","year":"2011","unstructured":"Padberg, M.W.: Node packings in graphs and claw free graphs. Optima 86, 8\u201310 (2011)","journal-title":"Optima"},{"issue":"1","key":"1502_CR30","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"MW Padberg","year":"1982","unstructured":"Padberg, M.W., Rao, M.R.: Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7(1), 67\u201380 (1982)","journal-title":"Math. Oper. Res."},{"key":"1502_CR31","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1016\/j.disc.2009.03.031","volume":"310","author":"A Pecher","year":"2010","unstructured":"Pecher, A., Wagler, A.: On facets of stable set polytopes of claw-free graphs with stability number three. Discrete Math. 310, 493\u2013498 (2010)","journal-title":"Discrete Math."},{"key":"1502_CR32","unstructured":"Pulleyblank W.R., Shepherd, F.B.: Formulations for the stable set polytope of a claw-free graph. In: Rinaldi, G., Wolsey, L. (eds.) Proceedings Third IPCO Conference, pp. 267\u2013279 (1993)"},{"issue":"6","key":"1502_CR33","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/3127497","volume":"64","author":"T Rothvoss","year":"2017","unstructured":"Rothvoss, T.: The matching polytope has exponential extension complexity. J. ACM 64(6), 41:1\u201341:19 (2017)","journal-title":"J. ACM"},{"key":"1502_CR34","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency (3 volumes). Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency (3 volumes). Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"key":"1502_CR35","unstructured":"Stauffer, G.: On the stable set polytope of claw-free graphs. PhD thesis, Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (2005)"},{"key":"1502_CR36","unstructured":"Weller, A., Jebara, T.: Revisiting the limits of MAP inference by MWSS on perfect graphs. In: Artificial Intelligence and Statistics, pp. 1061\u20131069 (2015)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01502-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01502-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01502-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T15:55:11Z","timestamp":1624377311000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01502-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,28]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["1502"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01502-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,4,28]]},"assertion":[{"value":"6 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}