{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T20:27:09Z","timestamp":1770323229591,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2008,1]]},"DOI":"10.1007\/s00493-008-2244-x","type":"journal-article","created":{"date-parts":[[2008,4,28]],"date-time":"2008-04-28T02:45:36Z","timestamp":1209350736000},"page":"45-67","source":"Crossref","is-referenced-by-count":46,"title":["The stable set polytope of quasi-line graphs"],"prefix":"10.1007","volume":"28","author":[{"given":"Friedrich","family":"Eisenbrand","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"}]},{"given":"Paolo","family":"Ventura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,4,29]]},"reference":[{"key":"2244_CR1","volume-title":"Network flows: Theory, algorithms, and applications","author":"R. K. Ahuja","year":"1993","unstructured":"R. K. Ahuja, T. L. Magnanti and J. B. Orlin: Network flows: Theory, algorithms, and applications, Prentice Hall Inc., Englewood Cliffs, NJ, 1993. MR 94e:90035"},{"key":"2244_CR2","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/3-540-47867-1_10","volume-title":"Integer programming and combinatorial optimization","author":"K. Andersen","year":"2002","unstructured":"K. Andersen, G. Cornu\u00e9jols and Y. Li: Split closure and intersection cuts, Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 2337, Springer, Berlin, 2002, pp. 127\u2013144. MR MR2061050"},{"key":"2244_CR3","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1287\/opre.28.5.1074","volume":"28","author":"J. J. Bartholdi III","year":"1980","unstructured":"J. J. Bartholdi III, J. B. Orlin and H. D. Ratliff: Cyclic scheduling via integer programs with circular ones, Operations Research 28 (1980), 1074\u20131085.","journal-title":"Operations Research"},{"issue":"2\u20133","key":"2244_CR4","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10107-002-0320-3","volume":"94","author":"A. Caprara","year":"2003","unstructured":"A. Caprara and A. N. Letchford: On the separation of split cuts and related inequalities, Mathematical Programming 94(2\u20133) (2003), 279\u2013294.","journal-title":"Mathematical Programming"},{"key":"2244_CR5","doi-asserted-by":"crossref","unstructured":"M. Chudnovsky: Personal communication, 2004.","DOI":"10.1103\/PhysRevLett.93.208901"},{"key":"2244_CR6","series-title":"London. Math. Soc. Lecture Notes","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1017\/CBO9780511734885.008","volume-title":"Surveys in Combinatorics, 2005","author":"M. Chudnovsky","year":"2005","unstructured":"M. Chudnovsky and P. Seymour: The structure of claw-free graphs, in Surveys in Combinatorics, 2005, (Proceedings of the 20th British Combinatorial Conference, Durham, 2005, B. S. Webb, ed.), London. Math. Soc. Lecture Notes 327, 153\u2013171."},{"key":"2244_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":"V. Chv\u00e1tal: Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Mathematics 4 (1973), 305\u2013337.","journal-title":"Discrete Mathematics"},{"key":"2244_CR8","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114\/115","author":"V. Chv\u00e1tal","year":"1989","unstructured":"V. Chv\u00e1tal, W. Cook and M. Hartmann: On cutting-plane proofs in combinatorial optimization, Linear Algebra and its Applications 114\/115 (1989), 455\u2013499.","journal-title":"Linear Algebra and its Applications"},{"key":"2244_CR9","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF01580858","volume":"47","author":"W. Cook","year":"1990","unstructured":"W. Cook, R. Kannan and A. Schrijver: Chv\u00e1tal closures for mixed integer programming problems, Mathematical Programming 47 (1990), 155\u2013174.","journal-title":"Mathematical Programming"},{"key":"2244_CR10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds: Maximum matching and a polyhedron with 0,1-vertices, Journal of Research of the National Bureau of Standards 69 (1965), 125\u2013130.","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"2244_CR11","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds: Paths, trees and flowers; Canadian Journal of Mathematics 17 (1965), 449\u2013467.","journal-title":"Canadian Journal of Mathematics"},{"issue":"2","key":"2244_CR12","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s004930050057","volume":"19","author":"F. Eisenbrand","year":"1999","unstructured":"F. Eisenbrand: On the membership problem for the elementary closure of a polyhedron, Combinatorica 19(2) (1999), 297\u2013300.","journal-title":"Combinatorica"},{"key":"2244_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jctb.1996.1715","volume":"69","author":"A. Galluccio","year":"1997","unstructured":"A. Galluccio and A. Sassano: The rank facets of the stable set polytope for claw-free graphs, Journal on Combinatorial Theory 69 (1997), 1\u201338.","journal-title":"Journal on Combinatorial Theory"},{"issue":"3","key":"2244_CR14","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1137\/S089548010343569X","volume":"19","author":"D. Gijswijt","year":"2005","unstructured":"D. Gijswijt: Integer decomposition for polyhedra defined by nearly totally unimodular matrices, SIAM Journal on Discrete Mathematics 19(3) (2005), 798\u2013806.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"3","key":"2244_CR15","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0095-8956(81)90033-2","volume":"31","author":"R. Giles","year":"1981","unstructured":"R. Giles and L. E. Trotter, JR: On stable set polyhedra for K 1,3-free graphs, J. Combin. Theory Ser. B 31(3) (1981), 313\u2013326. MR MR638287 (84a:05041)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2244_CR16","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"R. E. Gomory","year":"1958","unstructured":"R. E. Gomory: Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical Society 64 (1958), 275\u2013278.","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"2","key":"2244_CR17","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1(2) (1981), 169\u2013197.","journal-title":"Combinatorica"},{"key":"2244_CR18","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 Verlag, Berlin, 1988."},{"issue":"4","key":"2244_CR19","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1137\/0211053","volume":"11","author":"R. M. Karp","year":"1982","unstructured":"R. M. Karp and C. H. Papadimitriou: On linear characterizations of combinatorial optimization problems, SIAM Journal on Computing 11(4) (1982), 620\u2013632.","journal-title":"SIAM Journal on Computing"},{"key":"2244_CR20","first-page":"1093","volume":"244","author":"L. G. Khachiyan","year":"1979","unstructured":"L. G. Khachiyan: A polynomial algorithm in linear programming, Doklady Akademii Nauk SSSR 244 (1979), 1093\u20131097.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"2244_CR21","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s001860300317","volume":"59","author":"T. M. Liebling","year":"2004","unstructured":"T. M. Liebling, G. Oriolo, B. Spille and G. Stauffer: On the non-rank facets of the stable set polytope of claw-free graphs and circulant graphs, Mathematical Methods of Operations Research 59 (2004), 25\u201335.","journal-title":"Mathematical Methods of Operations Research"},{"key":"2244_CR22","volume-title":"Matching theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"L. Lov\u00e1sz and M. D. Plummer: Matching theory, North Holland, Amsterdam, 1986."},{"issue":"3","key":"2244_CR23","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0012-365X(83)90120-6","volume":"46","author":"J.-F. Maurras","year":"1983","unstructured":"J.-F. Maurras: Convex hull of the edges of a graph and near bipartite graphs, Discrete Math. 46(3) (1983), 257\u2013265. MR MR716446 (84m:05070)","journal-title":"Discrete Math."},{"key":"2244_CR24","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G. J. Minty","year":"1980","unstructured":"G. J. Minty: On maximal independent sets of vertices in claw-free graphs, Journal on Combinatorial Theory 28 (1980), 284\u2013304.","journal-title":"Journal on Combinatorial Theory"},{"issue":"2","key":"2244_CR25","doi-asserted-by":"crossref","first-page":"194","DOI":"10.15807\/jorsj.44.194","volume":"44","author":"D. Nakamura","year":"2001","unstructured":"D. Nakamura and A. Tamura: A revision of Minty\u2019s algorithm for finding a maximum weighted stable set of a claw-free graph, Journal of the Operations Research Society of Japan 44(2) (2001), 194\u20132004.","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"2244_CR26","doi-asserted-by":"crossref","unstructured":"G. L. Nemhauser and L. A. Wolsey: Integer and combinatorial optimization, John Wiley, 1988.","DOI":"10.1002\/9781118627372"},{"issue":"3","key":"2244_CR27","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0166-218X(03)00400-1","volume":"132","author":"G. Oriolo","year":"2003","unstructured":"G. Oriolo: Clique family inequalities for the stable set polytope for quasi-line graphs, Discrete Applied Mathematics 132(3) (2003), 185\u2013201.","journal-title":"Discrete Applied Mathematics"},{"key":"2244_CR28","volume-title":"The Russian method for linear programming III: Bounded integer programming","author":"M. W. Padberg","year":"1981","unstructured":"M. W. Padberg and M. R. Rao: The Russian method for linear programming III: Bounded integer programming, Tech. Report 81-39, New York University, Graduate School of Business and Administration, 1981."},{"key":"2244_CR29","unstructured":"W. R. Pulleyblank and F. B. Shepherd: Formulations for the stable set polytope of a claw-free graph, in: Proceedings Third IPCO Conference (G. Rinaldi and L. Wolsey, eds.), 1993, pp. 267\u2013279."},{"key":"2244_CR30","unstructured":"A. Ben Rebea: \u00c9tude des stables dans les graphes quasi-adjoints, Ph.D. thesis, Universit\u00e9 de Grenoble, 1981."},{"key":"2244_CR31","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N. Sbihi","year":"1980","unstructured":"N. Sbihi: Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile, Discrete Mathematics 29 (1980), 53\u201376.","journal-title":"Discrete Mathematics"},{"key":"2244_CR32","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/S0167-5060(08)70085-2","volume":"9","author":"A. Schrijver","year":"1980","unstructured":"A. Schrijver: On cutting planes, Annals of Discrete Mathematics 9 (1980), 291\u2013296.","journal-title":"Annals of Discrete Mathematics"},{"key":"2244_CR33","unstructured":"A. Schrijver: Theory of linear and integer programming, John Wiley, 1986."},{"key":"2244_CR34","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial optimization. Polyhedra and efficiency","author":"A. Schrijver","year":"2003","unstructured":"A. Schrijver: Combinatorial optimization. Polyhedra and efficiency, (3 volumes), Algorithms and Combinatorics 24, Springer, Berlin, 2003."},{"key":"2244_CR35","first-page":"353","volume":"71","author":"F. B. Shepherd","year":"1995","unstructured":"F. B. Shepherd: Applying Lehman\u2019s theorems to packing problems, Mathematical Programming 71 (1995), 353\u2013367.","journal-title":"Mathematical Programming"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-008-2244-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-008-2244-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-008-2244-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T21:32:45Z","timestamp":1559079165000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-008-2244-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["2244"],"URL":"https:\/\/doi.org\/10.1007\/s00493-008-2244-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}