{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T15:59:25Z","timestamp":1774022365720,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540745648","type":"print"},{"value":"9783540745655","type":"electronic"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74565-5_31","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T02:01:04Z","timestamp":1188007264000},"page":"412-426","source":"Crossref","is-referenced-by-count":41,"title":["A Stochastic Local Search Approach to Vertex Cover"],"prefix":"10.1007","author":[{"given":"Silvia","family":"Richter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Malte","family":"Helmert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles","family":"Gretton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.\u00a0H.\u00a0Freeman and Company (1979)"},{"issue":"12","key":"31_CR2","doi-asserted-by":"publisher","first-page":"3520","DOI":"10.1016\/j.cor.2005.03.030","volume":"33","author":"F.C. Gomes","year":"2006","unstructured":"Gomes, F.C., Meneses, C.N., Pardalos, P.M., Viana, G.V.R.: Experimental analysis of approximation algorithms for the vertex cover and set covering problems. Computers and Operations Research\u00a033(12), 3520\u20133534 (2006)","journal-title":"Computers and Operations Research"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00453-006-1214-1","volume":"45","author":"F.N. Abu-Khzam","year":"2006","unstructured":"Abu-Khzam, F.N., Langston, M.A., Shanbhag, P., Symons, C.T.: Scalable parallel algorithms for FPT problems. Algorithmica\u00a045, 269\u2013284 (2006)","journal-title":"Algorithmica"},{"key":"31_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BFb0040790","volume-title":"Evolutionary Programming VII","author":"I.K. Evans","year":"1998","unstructured":"Evans, I.K.: Evolutionary algorithms for vertex cover. In: Porto, V.W., Waagen, D. (eds.) Evolutionary Programming VII. LNCS, vol.\u00a01447, pp. 377\u2013386. Springer, Heidelberg (1998)"},{"key":"31_CR5","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithmic Number Theory","author":"S. Gilmour","year":"2006","unstructured":"Gilmour, S., Dras, M.: Kernelization as heuristic structure for the vertex cover problem. In: Hess, F., Pauli, S., Pohst, M. (eds.) Algorithmic Number Theory. LNCS, vol.\u00a04076, Springer, Heidelberg (2006)"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity: A framework for systematically confronting computational intractability. In: Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future. DIMACS Series, vol.\u00a049, pp. 49\u201399 (1999)","DOI":"10.1090\/dimacs\/049\/04"},{"key":"31_CR7","unstructured":"Xu, K.: BHOSLIB: Benchmarks with hidden optimum solutions for graph problems (maximum clique, maximum independent set, minimum vertex cover and vertex coloring) \u2013 hiding exact solutions in random graphs. Web site, http:\/\/www.nlsde.buaa.edu.cn\/~kexu\/benchmarks\/graph-benchmarks.htm"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Niedermeier, R., Rossmanith, P.: Upper bounds for vertex cover further improved. In: STACS 1999. Proceedings of the 16th Symposium on Theoretical Aspects in Computer Science, pp. 561\u2013570 (1999)","DOI":"10.1007\/3-540-49116-3_53"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/S0022-0000(03)00075-8","volume":"67","author":"J. Cheetham","year":"2003","unstructured":"Cheetham, J., Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.J.: Solving large FPT problems on coarse grained parallel machines. Journal of Computer and System Sciences\u00a067, 691\u2013706 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\u20134","key":"31_CR10","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1023\/B:ANOR.0000039523.95673.33","volume":"131","author":"S.J. Shyu","year":"2004","unstructured":"Shyu, S.J., Yin, P.Y., Lin, B.M.T.: An ant colony optimization algorithm for the minimum weight vertex cover problem. Annals of Operations Research\u00a0131(1\u20134), 283\u2013304 (2004)","journal-title":"Annals of Operations Research"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Trick, M.A. (eds.): Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge. DIMACS Series, vol.\u00a026. American Mathematical Society (1996)","DOI":"10.1090\/dimacs\/026"},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s10878-004-4835-9","volume":"8","author":"V.C. Barbosa","year":"2004","unstructured":"Barbosa, V.C., Campos, L.C.D.: A novel evolutionary formulation of the maximum independent set problem. Journal of Combinatorial Optimization\u00a08, 419\u2013437 (2004)","journal-title":"Journal of Combinatorial Optimization"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1023\/A:1014899909753","volume":"6","author":"S. Busygin","year":"2002","unstructured":"Busygin, S., Butenko, S., Pardalos, P.M.: A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere. Journal of Combinatorial Optimization\u00a06, 287\u2013297 (2002)","journal-title":"Journal of Combinatorial Optimization"},{"key":"31_CR14","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1613\/jair.1815","volume":"25","author":"W. Pullan","year":"2006","unstructured":"Pullan, W., Hoos, H.H.: Dynamic local search for the maximum clique problem. Journal of Artificial Intelligence Research\u00a025, 159\u2013185 (2006)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10878-006-9635-y","volume":"12","author":"W. Pullan","year":"2006","unstructured":"Pullan, W.: Phased local search for the maximum clique problem. Journal of Combinatorial Optimization\u00a012, 303\u2013323 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"key":"31_CR16","volume-title":"Stochastic Local Search: Foundations and Applications","author":"H.H. Hoos","year":"2004","unstructured":"Hoos, H.H., St\u00fctzle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, San Francisco (2004)"},{"key":"31_CR17","doi-asserted-by":"crossref","first-page":"61","DOI":"10.3233\/SAT190017","volume":"2","author":"O. Kullmann","year":"2005","unstructured":"Kullmann, O.: The SAT 2005 solver competition on random instances. Journal on Satisfiability, Boolean Modeling and Computation\u00a02, 61\u2013102 (2005)","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"31_CR18","unstructured":"Selman, B., Kautz, H.A.: Domain-independent extensions to GSAT: Solving large structured satisfiability problems. In: IJCAI 1993. Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, pp. 290\u2013295 (1993)"},{"key":"31_CR19","unstructured":"Thornton, J., Pham, D.N., Bain, S., Ferreira Jr., V.: Additive versus multiplicative clause weighting for SAT. In: AAAI 2004. Proceedings of the Nineteenth National Conference on Artificial Intelligence, pp. 191\u2013196 (2004)"},{"key":"31_CR20","unstructured":"Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: A simple model to generate hard satisfiable instances. In: IJCAI 2005. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, pp. 337\u2013342 (2005)"},{"key":"31_CR21","unstructured":"Le Berre, D., Simon, L.: The SAT 2004 competition. Web site, http:\/\/www.lri.fr\/~simon\/contest04\/results\/"},{"key":"31_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/978-3-540-45193-8_34","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"L. Liu","year":"2003","unstructured":"Liu, L., Truszczynski, M.: Local-search techniques for propositional logic extended with cardinality constraints. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 495\u2013509. Springer, Heidelberg (2003)"},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"Brockington, M., Culberson, J.C.: Camouflaging independent sets in quasi-random graphs, pp. 75\u201388 [11]","DOI":"10.1090\/dimacs\/026\/05"}],"container-title":["Lecture Notes in Computer Science","KI 2007: Advances in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74565-5_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,26]],"date-time":"2020-04-26T00:10:55Z","timestamp":1587859855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74565-5_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540745648","9783540745655"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74565-5_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007]]}}}