{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:01Z","timestamp":1725663301422},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540127277"},{"type":"electronic","value":"9783540387145"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1983]]},"DOI":"10.1007\/3-540-12727-5_20","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T12:55:04Z","timestamp":1330174504000},"page":"332-340","source":"Crossref","is-referenced-by-count":0,"title":["Probabilistic analysis of graph colouring algorithms"],"prefix":"10.1007","author":[{"given":"A.","family":"Marchetti-Spaccamela","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Talamo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"B. BOLLOBAS, P. ERD\u00d6S: Cliques in random graphs. Math. Proc. Camb. Phil. Soc., vol. 80, (1976).","key":"20_CR1","DOI":"10.1017\/S0305004100053056"},{"unstructured":"P. ERD\u00d6S, A. RENYI: On random graphs 1. Publ. Math., vol. 6, (1959).","key":"20_CR2"},{"issue":"1","key":"20_CR3","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/321921.321926","volume":"33","author":"M. R. Garey","year":"1976","unstructured":"M.R. GAREY, D.S. JOHNSON: The complexity of near-optimal graph colouring. J. ACM, vol. 33, n. 1, pp. 43\u201346 (1976).","journal-title":"J. ACM"},{"unstructured":"M.R. GAREY, D.S. JOHNSON: Computers and intractability: a guide to the theory of NP-completeness. Freeman San Francisco (1978).","key":"20_CR4"},{"key":"20_CR5","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G. R. Grimett","year":"1975","unstructured":"G.R. GRIMETT, C.J.H. Mc DIARMID: On colouring random graphs. Math. Proc. Camb. Phil. Soc., vol. 77, pp. 313\u2013324, (1975).","journal-title":"Math. Proc. Camb. Phil. Soc."},{"unstructured":"R.M. KAPP: The probabilistic analysis of some combinatorial search algorithms. In J.F. Traub (ed.), Algorithms and complexity J.F. Traud, Academic Press (1976).","key":"20_CR6"},{"doi-asserted-by":"crossref","unstructured":"E.L. LAWLER: A note on the complexity of the chromatic number. Inf. Proc. Let. (1976).","key":"20_CR7","DOI":"10.1016\/0020-0190(76)90065-X"},{"unstructured":"C.J.H. Mc DIARMID: Determining the chromatic number of a graph. SIAM J. on Comp. (1981).","key":"20_CR8"},{"unstructured":"M. TALAMO: Analisi probabilistica della complessit\u00e0 di algoritmi di colorazione. Thesis Universit\u00e0 di Roma (1981).","key":"20_CR9"},{"unstructured":"M. TALAMO: A probabilistic of some greedy algorithms. Technical Report R.12 Istituto di Automatica, Universit\u00e0 di Roma (1983).","key":"20_CR10"}],"container-title":["Lecture Notes in Computer Science","CAAP'83"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-12727-5_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:06:13Z","timestamp":1605625573000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-12727-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983]]},"ISBN":["9783540127277","9783540387145"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-12727-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1983]]}}}