{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:17Z","timestamp":1725663617306},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540551218"},{"type":"electronic","value":"9783540467359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_13","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:47:39Z","timestamp":1330249659000},"page":"135-147","source":"Crossref","is-referenced-by-count":0,"title":["Fast parallel algorithms for coloring random graphs"],"prefix":"10.1007","author":[{"given":"Zvi M.","family":"Kedem","sequence":"first","affiliation":[]},{"given":"Krishna V.","family":"Palem","sequence":"additional","affiliation":[]},{"given":"Grammati E.","family":"Pantziou","sequence":"additional","affiliation":[]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[]},{"given":"Christos D.","family":"Zaroliagis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"13_CR1","volume-title":"Random Graphs","author":"B. Bollobas","year":"1985","unstructured":"B. Bollobas, \u201cRandom Graphs\u201d, Academic Press, London, 1985."},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff, \u201cA measure of asymptotic efficiency for tests based on the sum of observations\u201d, Ann. Math. Statist. 23 (1952), 493\u2013509.","journal-title":"Ann. Math. Statist."},{"issue":"No.l","key":"13_CR3","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1002\/rsa.3240010104","volume":"1","author":"A. Calkin","year":"1990","unstructured":"A. Calkin, A. Frieze, \u201cProbabilistic Analysis of a Parallel Algorithm for Finding Maximal Independent Sets\u201d, Random Structures & Algorithms, Vol.1, No.l, 39\u201350, 1990.","journal-title":"Random Structures & Algorithms"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, P. Raghavan, M. Tompa, \u201cParallel Graph Algorithms that are Efficient on Average\u201d, Proc. of the 28th Annual IEEE FOCS, 1987, pp.260\u2013269.","DOI":"10.1109\/SFCS.1987.46"},{"key":"13_CR5","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M. E. Dyer","year":"1989","unstructured":"M. E. Dyer, A. M. Frieze, \u201cThe Solution of Some Random NP-hard Problems in Polynomial Expected Time\u201d, Journal of Algorithms, 10, 451\u2013489, 1989.","journal-title":"Journal of Algorithms"},{"key":"13_CR6","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erdos","year":"1959","unstructured":"P. Erdos, A. Renyi, \u201cOn random graphs I\u201d, Publ. Math. Debrecen, 6 (1959), 290\u2013297.","journal-title":"Publ. Math. Debrecen"},{"key":"13_CR7","unstructured":"Z. Kedem, K. Palem, P. Spirakis, \u201cAdaptive average case analysis\u201d, unpublished manuscript, 1990."},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"L. Kucera, \u201cExpected behaviour of graph coloring algorithms\u201d, Proc. of Fundamentals in Computation Theory LNCS, Vol.56, pp.447\u2013451, Springer-Verlag, 1977.","DOI":"10.1007\/3-540-08442-8_114"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.2307\/1426408","volume":"1","author":"J.E. Littlewood","year":"1969","unstructured":"J.E. Littlewood, \u201cOn the probability in the tail of a binomial distribution\u201d, Adv. Appl. Probab., 1(1969), 43\u201372.","journal-title":"Adv. Appl. Probab."},{"key":"13_CR10","volume-title":"CTI TR-90.10.25","author":"G. Pantziou","year":"1990","unstructured":"G. Pantziou, P. Spirakis, C. Zaroliagis, \u201cColoring Random Graphs Efficiently in Parallel, through Adaptive Techniques\u201d, CTI TR-90.10.25, Computer Technology Institute, Patras. Also presented in the ALCOM Workshop on Graph Algorithms, Data Structures and Computational Geometry, Berlin 3\u20135 October, 1990."},{"key":"13_CR11","unstructured":"J. Spencer, \u201cTen Lectures on the Probabilistic Method\u201d, SIAM, 1987."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55121-2_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T18:14:54Z","timestamp":1687284894000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}