{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:24:31Z","timestamp":1725665071935},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:22:31Z","timestamp":1330280551000},"page":"43-53","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Greedily approximating the r-independent set and k-center problems on random instances"],"prefix":"10.1007","author":[{"given":"Bernd","family":"Kreuter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Nierhoff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"4_CR1","unstructured":"N. Alon, J. H. Spencer, and P. Erd\u00f3s. The Probabilistic Method. Wiley, 1992."},{"key":"4_CR2","unstructured":"B. Bollob\u00e1s. Random Graphs. Academic Press, 1985."},{"issue":"4","key":"4_CR3","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1137\/1119080","volume":"19","author":"Y. D. Burtin","year":"1974","unstructured":"Y. D. Burtin. On extreme metric parameters of a random graph: I. asymptotic estimates. Theory of Probability and its Applications, 19(4):710\u2013725, 1974.","journal-title":"Theory of Probability and its Applications"},{"issue":"1","key":"4_CR4","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/1120007","volume":"20","author":"Y. D. Burtin","year":"1975","unstructured":"Y. D. Burtin. On extreme metric characteristics of a random graph: II. limit distributions. Theory of Probability and its Applications, 20(1):83\u2013101, 1975.","journal-title":"Theory of Probability and its Applications"},{"issue":"3","key":"4_CR5","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1137\/0605034","volume":"5","author":"G. J. Chang","year":"1984","unstructured":"G. J. Chang and G. L. Nemhauser. The k-domination and k-stability problems on sun-free chordal graphs. SIAM Journal on Algebraic Discrete Methods, 5(3):332\u2013345, 1984.","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A. Frieze","year":"1997","unstructured":"A. Frieze and C. McDiarmid. Algorithmic theory of random graphs. Random Structures & Algorithms, 10:5\u201342, 1997.","journal-title":"Random Structures & Algorithms"},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0012-365X(90)90149-C","volume":"81","author":"A. M. Frieze","year":"1990","unstructured":"A. M. Frieze. On the independence number of random graphs. Discrete Mathematics, 81:171\u2013175, 1990.","journal-title":"Discrete Mathematics"},{"key":"4_CR8","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G. R. Grimmett","year":"1975","unstructured":"G. R. Grimmett and C. McDiarmid. On colouring random graphs. Proceedings of the Cambridge Philosophical Society, 77:313\u2013324, 1975.","journal-title":"Proceedings of the Cambridge Philosophical Society"},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0012-365X(90)90365-O","volume":"86","author":"S. T. Hedetniemi","year":"1990","unstructured":"S. T. Hedetniemi and R. C. Laskar. Bibliography on domination in graphs and some basic definitions of domination parameters. Discrete Mathematics, 86:257\u2013277, 1990.","journal-title":"Discrete Mathematics"},{"key":"4_CR10","first-page":"189","volume":"25","author":"D. S. Hochbaum","year":"1985","unstructured":"D. S. Hochbaum. Easy solutions for the k-center problem or the dominating set problem on random graphs. Annals of Discrete Mathematics, 25:189\u2013210, 1985.","journal-title":"Annals of Discrete Mathematics"},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF01874388","volume":"1","author":"C. McDiarmid","year":"1984","unstructured":"C. McDiarmid. Colouring random graphs. Annals of Operations Research, 1:183\u2013200, 1984.","journal-title":"Annals of Operations Research"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63248-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:53:47Z","timestamp":1578509627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_4"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"7 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}