{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T10:31:40Z","timestamp":1725532300191},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020162"},{"type":"electronic","value":"9783642020179"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02017-9_43","type":"book-chapter","created":{"date-parts":[[2009,5,11]],"date-time":"2009-05-11T15:38:06Z","timestamp":1242056286000},"page":"410-419","source":"Crossref","is-referenced-by-count":1,"title":["Greedy Local Search and Vertex Cover in Sparse Random Graphs"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Witt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"43_CR1","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1002\/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#","volume":"12","author":"J. Aronson","year":"1998","unstructured":"Aronson, J., Frieze, A., Pittel, B.G.: Maximum matchings in sparse random graphs: Karp-Sipser revisited. Random Structures and Algorithms\u00a012(2), 111\u2013177 (1998)","journal-title":"Random Structures and Algorithms"},{"issue":"3","key":"43_CR2","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s10051-001-8683-4","volume":"24","author":"M. Bauer","year":"2001","unstructured":"Bauer, M., Golinelli, O.: Core percolation in random graphs: a critical phenomena analysis. The European Physical Journal B\u00a024(3), 339\u2013352 (2001)","journal-title":"The European Physical Journal B"},{"key":"43_CR3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"key":"43_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"43_CR5","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.) EP 1998. LNCS, vol.\u00a01447, pp. 377\u2013386. Springer, Heidelberg (1998)"},{"key":"43_CR6","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, 3rd edn., vol.\u00a01. Wiley, Chichester (1968)","edition":"3"},{"key":"43_CR7","doi-asserted-by":"crossref","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. In: Proc. of GECCO\u00a02007, pp. 797\u2013804. AMC Press (2007)","DOI":"10.1145\/1276958.1277118"},{"issue":"1","key":"43_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1162\/evco.2009.17.1.3","volume":"17","author":"T. Friedrich","year":"2009","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Analyses of simple hybrid evolutionary algorithms for the vertex cover problem. Evolutionary Computation\u00a017(1), 3\u201320 (2009)","journal-title":"Evolutionary Computation"},{"issue":"1","key":"43_CR9","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1002\/rsa.20072","volume":"28","author":"D. Gamarnik","year":"2005","unstructured":"Gamarnik, D., Nowicki, T., Swirscsz, G.: Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method. Random Structures and Algorithms\u00a028(1), 76\u2013106 (2005)","journal-title":"Random Structures and Algorithms"},{"key":"43_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/3-540-36494-3_37","volume-title":"STACS 2003","author":"O. Giel","year":"2003","unstructured":"Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 415\u2013426. Springer, Heidelberg (2003)"},{"key":"43_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0304-3975(01)00163-3","volume":"265","author":"A. Hartmann","year":"2001","unstructured":"Hartmann, A., Weigt, M.: Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs. Theoretical Computer Science\u00a0 (265), 199\u2013225 (2001)","journal-title":"Theoretical Computer Science"},{"key":"43_CR12","first-page":"364","volume-title":"Proc. of FOCS 1981","author":"R.M. Karp","year":"1981","unstructured":"Karp, R.M., Sipser, M.: Maximum matchings in sparse random graphs. In: Proc. of FOCS 1981, pp. 364\u2013375. IEEE Press, Los Alamitos (1981)"},{"issue":"1","key":"43_CR13","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F. Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science\u00a0378(1), 32\u201340 (2007)","journal-title":"Theoretical Computer Science"},{"key":"43_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/11940128_62","volume-title":"Algorithms and Computation","author":"F. Neumann","year":"2006","unstructured":"Neumann, F., Witt, C.: Runtime analysis of a simple ant colony optimization algorithm. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 618\u2013627. Springer, Heidelberg (2006); Extended version to appear in Algorithmica"},{"key":"43_CR15","first-page":"1870","volume-title":"Proc. of CEC\u00a02007","author":"P.S. Oliveto","year":"2007","unstructured":"Oliveto, P.S., He, J., Yao, X.: Evolutionary algorithms and the vertex cover problem. In: Proc. of CEC\u00a02007, pp. 1870\u20131877. IEEE Press, Los Alamitos (2007)"},{"key":"43_CR16","first-page":"547","volume-title":"Proc. of GECCO\u00a02007","author":"M. Pelikan","year":"2007","unstructured":"Pelikan, M., Kalapala, R., Hartmann, A.K.: Hybrid evolutionary algorithms on minimum vertex cover for random graphs. In: Proc. of GECCO\u00a02007, pp. 547\u2013554. ACM Press, New York (2007)"},{"issue":"3","key":"43_CR17","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R.E. Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM Journal on Computing\u00a06(3), 537\u2013546 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"43_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/11523468_48","volume-title":"Automata, Languages and Programming","author":"I. Wegener","year":"2005","unstructured":"Wegener, I.: Simulated annealing beats metropolis in combinatorial optimization. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 589\u2013601. Springer, Heidelberg (2005)"},{"key":"43_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/978-3-540-31856-9_4","volume-title":"STACS 2005","author":"C. Witt","year":"2005","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 44\u201356. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02017-9_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T10:17:34Z","timestamp":1619777854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02017-9_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020162","9783642020179"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02017-9_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}