{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:16Z","timestamp":1725664036453},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578994"},{"type":"electronic","value":"9783540483854"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_50","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:39:51Z","timestamp":1330263591000},"page":"166-176","source":"Crossref","is-referenced-by-count":0,"title":["Coloring k-colorable graphs in constant expected parallel time"],"prefix":"10.1007","author":[{"given":"Lud\u011bk","family":"Ku\u010dera","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, and M. Ben-Or, A theorem on probabilistic constant depth computation, Proceedings of the 16th Symposium on Theory of Computing, (1984), 471\u2013474.","DOI":"10.1145\/800057.808715"},{"key":"15_CR2","volume-title":"The probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. Spencer, and P. Erd\u0151s, The probabilistic Method, J. Wiley and Sons, New York, 1992."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s, The chromatic number of random graphs, Combinatorica 8, 49\u201356.","DOI":"10.1007\/BF02122551"},{"key":"15_CR4","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0020-0190(87)90163-3","volume":"25","author":"B. Brustmann","year":"1987","unstructured":"B. Brustmann, and I. Wegener, The complexity of symmetric functions in bounded depth circuits, Information Processing Letters 25 (1987), 217\u2013219.","journal-title":"Information Processing Letters"},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff, A measure of asymptotic efficiency for tests based on the sum of observations, Ann. Math. Statist. 23 (1952), 493\u2013509.","journal-title":"Ann. Math. Statist."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"B. Chlebus, K. Diks, T. Hagerup, and T. Radzik, Efficient simulations between CRCW PRAMs, Proc. 13th Symp. on the Mathematical Foundations of Computer Science, 1988, 230\u2013239.","DOI":"10.1007\/3-540-51498-8_9"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, P. Raghavan, and M. Tompa, Parallel graph algorithms that are efficient on average, Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, (1987), 260\u2013269.","DOI":"10.1109\/SFCS.1987.46"},{"key":"15_CR8","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M. Dyer","year":"1989","unstructured":"M. Dyer, and A. Frieze, The solution of some random NP-hard problems in polynomial expected time, J Algorithms 10 (1989), 451\u2013489.","journal-title":"J Algorithms"},{"key":"15_CR9","unstructured":"A. Frieze, and L. Ku\u010dera, Parallel colouring of random graphs, in Random Graphs 87, M. Karonski, J. Jaworski, A. Rucinski, eds, J. Wiley 1990, 41\u201352"},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, and D. S. Johnson, The complexity of near optimal graph coloring, JACM 23 (1976), 43\u201349.","journal-title":"JACM"},{"key":"15_CR11","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. J. H. McDiarmid, On colouring random graphs, Math. Proc. Cambridge Phil. Soc., 77 (1975), 313\u2013324.","journal-title":"Math. Proc. Cambridge Phil. Soc."},{"key":"15_CR12","unstructured":"J. H\u00e5stad, I. Wegener, N. Wurm, and S.-Z. Yi, Optimal depth, very small size circuits for symmetric functions in AC0, Tech. Rep. 384, Univ. Dortmund (1991)."},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science 56","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/3-540-08442-8_114","volume-title":"FCT'77","author":"L. Ku\u010dera","year":"1977","unstructured":"L. Ku\u010dera, Expected behavior of graph coloring algorithms, in FCT'77, M. Karpinski, ed., Lecture Notes in Computer Science 56 (Springer, Berlin, 1977), 447\u2013451."},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","volume":"14","author":"L. Ku\u010dera","year":"1982","unstructured":"L. Ku\u010dera, Parallel computation and conflicts in memory access, Information Processing Letters 14 (1982), 93\u201396.","journal-title":"Information Processing Letters"},{"key":"15_CR15","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0020-0190(89)90200-7","volume":"30","author":"L. Ku\u010dera","year":"1989","unstructured":"L. Ku\u010dera, Graphs with small chromatic numbers are easy to color, Information Processing Letters 30 (1989), 233\u2013236.","journal-title":"Information Processing Letters"},{"key":"15_CR16","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1016\/0196-6774(91)90040-6","volume":"12","author":"L. Ku\u010dera","year":"1991","unstructured":"L. Ku\u010dera, The greedy coloring is a bad probabilistic algorithm, J Algorithms, 12 (1991), 674\u2013684.","journal-title":"J Algorithms"},{"key":"15_CR17","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"L. Levin, Average case complete problems, SIAM J. Computing 15 (1986), 285\u2013286.","journal-title":"SIAM J. Computing"},{"key":"15_CR18","unstructured":"D. Matula, and L. Ku\u010dera, An expose-and-merge algorithm and the chromatic number of a random graph, in Random Graphs'87, M.Karonski, J.Jaworski, A.Rucinski, eds., (J.Wiley and Sons, 1990), 175\u2013187."},{"key":"15_CR19","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0020-0190(87)90216-X","volume":"25","author":"S. Moran","year":"1987","unstructured":"S. Moran, Generalized lower bound derived from H\u00e5stad's main lemma, Information Processing Letters 25 (1987), 383\u2013388.","journal-title":"Information Processing Letters"},{"key":"15_CR20","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1007\/BFb0032071","volume":"443","author":"P. Ragde","year":"1990","unstructured":"P. Ragde, The parallel simplicity of compaction and chaining, ICALP'90, Lecture Notes in Computer Science 443, 744\u2013751, 1990.","journal-title":"Lecture Notes in Computer Science"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"L. Stockmayer, The complexity of approximate computing, Proceedings of the 15th Symposium on Theory of Computing (1983), 118\u2013126.","DOI":"10.1145\/800061.808740"},{"key":"15_CR22","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0196-6774(88)90005-3","volume":"9","author":"J. Turner","year":"1988","unstructured":"J. Turner, Almost all k-colorable graphs are easy to color, J. Algorithms 9 (1988), 63\u201382.","journal-title":"J. Algorithms"}],"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-57899-4_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T18:36:27Z","timestamp":1687286187000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}