{"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":1771329231465,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,9,3]],"date-time":"2009-09-03T00:00:00Z","timestamp":1251936000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,5]]},"DOI":"10.1007\/s10878-009-9264-3","type":"journal-article","created":{"date-parts":[[2009,9,2]],"date-time":"2009-09-02T14:06:03Z","timestamp":1251900363000},"page":"434-457","source":"Crossref","is-referenced-by-count":46,"title":["A Branch and Cut solver for the maximum stable set problem"],"prefix":"10.1007","volume":"21","author":[{"given":"Steffen","family":"Rebennack","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Oswald","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk Oliver","family":"Theis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanna","family":"Seitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard","family":"Reinelt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panos M.","family":"Pardalos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,9,3]]},"reference":[{"key":"9264_CR1","unstructured":"ABACUS (2006) A branch and cut solver. Version 2.3.0. http:\/\/www.informatik.uni-koeln.de\/abacus\/"},{"key":"9264_CR2","series-title":"LNCS","first-page":"157","volume-title":"Computational combinatorial optimization","author":"D Applegate","year":"2001","unstructured":"Applegate D, Bixby R, Chv\u00e1tal V, Cook W (2001) TSP cuts which do not conform to the template paradigm. In: Computational combinatorial optimization. LNCS, vol 2241. Springer, Berlin, pp 157\u2013222"},{"key":"9264_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/SFCS.1992.267824","volume-title":"Proceedings 33rd IEEE symposium on foundations of computer science","author":"S Arora","year":"1992","unstructured":"Arora S, Safra S (1992) Probabilistic checking of proofs; a new characterization of NP. In: Proceedings 33rd IEEE symposium on foundations of computer science. IEEE Computer Society, Los Angeles, pp 2\u201313"},{"issue":"5","key":"9264_CR4","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1287\/opre.1070.0397","volume":"55","author":"A Avenali","year":"2007","unstructured":"Avenali A (2007) Resolution branch and bound and an application: the maximum weighted stable set problem. Oper Res 55(5):932\u2013948","journal-title":"Oper Res"},{"issue":"4","key":"9264_CR5","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1137\/0215075","volume":"14","author":"E Balas","year":"1986","unstructured":"Balas E, Yu CS (1986) Finding a maximum clique in an arbitrary graph. SIAM J Comput 14(4):1054\u20131068","journal-title":"SIAM J Comput"},{"key":"9264_CR6","volume-title":"The maximum clique problem. Handbook of combinatorial optimization","author":"IM Bomze","year":"1999","unstructured":"Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. Handbook of combinatorial optimization. Kluwer Academic, Boston"},{"key":"9264_CR7","unstructured":"Butenko S (2003) Maximum independent set and related problems, with applications. PhD thesis, University of Florida, USA"},{"key":"9264_CR8","unstructured":"Campelo M, Correa RC (2009) A Lagrangian relaxation for the maximum stable set problem. http:\/\/arxiv.org\/PS_cache\/arxiv\/pdf\/0903\/0903.1407v1.pdf"},{"issue":"1","key":"9264_CR9","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s101079900107","volume":"87","author":"A Caprara","year":"2000","unstructured":"Caprara A, Fiscetti M, Letchford AN (2000) On the separation of maximally violated mod-k cuts. Math Program 87(1):37\u201356","journal-title":"Math Program"},{"issue":"3","key":"9264_CR10","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1287\/ijoc.15.3.284.16077","volume":"15","author":"S Vries de","year":"2003","unstructured":"de Vries S, Vohra RV (2003) Combinatorial auctions: a survey. INFORMS J Comput 15(3):284\u2013309","journal-title":"INFORMS J Comput"},{"key":"9264_CR11","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s10107-006-0026-z","volume":"109","author":"I Dukanovich","year":"2007","unstructured":"Dukanovich I, Rendl F (2007) Semidefinite programming relaxations for graph coloring and maximal clique problems. Math Prog B 109:345\u2013365","journal-title":"Math Prog B"},{"key":"9264_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-45586-8_5","volume-title":"Computational combinatorial optimization","author":"M Elf","year":"2001","unstructured":"Elf M, Gutwenger C, J\u00fcnger M, Rinaldi G (2001) Branch-and-cut algorithms for combinatorial optimization and their implementation in ABACUS. In: Computational combinatorial optimization. LNCS, vol 2241. Springer, Berlin, pp 157\u2013222"},{"key":"9264_CR13","unstructured":"Fricke L (2007)"},{"key":"9264_CR14","first-page":"135","volume":"75","author":"K Fujisawa","year":"1995","unstructured":"Fujisawa K, Morito S, Kubo M (1995) Experimental analyses of the life span method for the maximum stable set problem. Inst Stat Math Coop Res Rep 75:135\u2013165","journal-title":"Inst Stat Math Coop Res Rep"},{"key":"9264_CR15","volume-title":"Computers and intractability, a guide to the theory of NP-completeness. A series of books in the mathematical sciences","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) In: Klee V (ed) Computers and intractability, a guide to the theory of NP-completeness. A series of books in the mathematical sciences. Freeman, New York"},{"key":"9264_CR16","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579262","volume":"6","author":"AMH Gerards","year":"1986","unstructured":"Gerards AMH, Schrijver A (1986) Matrices with the Edmonds-Johnson property. Combinatorica 6:365\u2013379","journal-title":"Combinatorica"},{"key":"9264_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combiantorial optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M, Lovasz L, Schrijver A (1988) Geometric algorithms and combiantorial optimization. Springer, Berlin"},{"key":"9264_CR18","doi-asserted-by":"crossref","first-page":"1014","DOI":"10.1137\/S1052623401394092","volume":"13","author":"G Gruber","year":"2003","unstructured":"Gruber G, Rendl F (2003) Computational experience with stable set relaxations. SIAM J Opt 13:1014\u20131028","journal-title":"SIAM J Opt"},{"key":"9264_CR19","unstructured":"ILOG CPLEX, Version 8.100. http:\/\/www.ilog.com\/products\/cplex\/"},{"key":"9264_CR20","first-page":"249","volume-title":"DIMACS series in discrete mathematics and theoretical computer science","author":"C Mannino","year":"1996","unstructured":"Mannino C, Sassano A (1996) Edge projection and the maximum cardinality stable set problem. In: DIMACS series in discrete mathematics and theoretical computer science, vol\u00a026. AMS, New York, pp\u00a0249\u2013261"},{"key":"9264_CR21","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1057\/jors.1992.71","volume":"43","author":"GL Nemhauser","year":"1992","unstructured":"Nemhauser GL, Sigismondi G (1992) A strong cutting plane\/branch-and-bound algorithm for node packing. J Oper Res Soc 43:443\u2013457","journal-title":"J Oper Res Soc"},{"key":"9264_CR22","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser GL, Trotter LE Jr (1975) Vertex packings: structural properties and algorithms. Math Program 8:232\u2013248","journal-title":"Math Program"},{"key":"9264_CR23","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"MW Padberg","year":"1973","unstructured":"Padberg MW (1973) On the facial structure of set packing polyhedra. Math Program 5:199\u2013215","journal-title":"Math Program"},{"key":"9264_CR24","unstructured":"Rebennack S (2006) Maximum stable set problem: a branch & cut solver. Diplomarbeit, Ruprecht\u2013Karls Universit\u00e4t Heidelberg, Heidelberg, Germany"},{"key":"9264_CR25","doi-asserted-by":"crossref","first-page":"3676","DOI":"10.1007\/978-0-387-74759-0_634","volume-title":"Encyclopedia of optimization","author":"S Rebennack","year":"2008","unstructured":"Rebennack S (2008) Stable set problem: branch & cut algorithms. In: Floudas CA, Pardalos PM (eds) Encyclopedia of optimization, 2nd edn. Springer, Berlin, pp 3676\u20133688","edition":"2"},{"key":"9264_CR26","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 (2001) A branch-and-cut algorithm for the maximum cardinality stable set problem. Oper Res Lett 28:63\u201374","journal-title":"Oper Res Lett"},{"key":"9264_CR27","unstructured":"Second DIMACS Challenge (1992\/1993). http:\/\/mat.gsia.cmu.edu\/challenge.html"},{"issue":"4","key":"9264_CR28","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1287\/ijoc.10.4.438","volume":"10","author":"EC Sewell","year":"1998","unstructured":"Sewell EC (1998) A branch and bound algorithm for the stability number of a sparse graph. INFORMS J Comput 10(4):438\u2013447","journal-title":"INFORMS J Comput"},{"key":"9264_CR29","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/opre.1040.0189","volume":"53","author":"DM Strickland","year":"2005","unstructured":"Strickland DM, Barnes E, Sokol JS (2005) Optimal protein structure alignment using maximum cliques. Oper Res 53:389\u2013402","journal-title":"Oper Res"},{"key":"9264_CR30","unstructured":"Warren JS, Hicks IV (2006) Combinatorial branch-and-bound for the maximum weight independent set problem. http:\/\/ie.tamu.edu\/people\/faculty\/Hicks\/jeff.rev.pdf"},{"key":"9264_CR31","unstructured":"Warrier D (2007) A branch, price, and cut appraoch to solving the maximum weighted independent set problem. PhD thesis, Texas A&M University"},{"issue":"4","key":"9264_CR32","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1002\/net.20088","volume":"46","author":"D Warrier","year":"2005","unstructured":"Warrier D, Wilhelm WE, Warren JS, Hicks IV (2005) A branch-and-price approach for the maximum weight independent set proble. Networks 46(4):198\u2013209","journal-title":"Networks"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9264-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9264-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9264-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T07:06:52Z","timestamp":1710572812000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9264-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,3]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["9264"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9264-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,3]]}}}