{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:10:47Z","timestamp":1761621047286,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540232414"},{"type":"electronic","value":"9783540302018"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30201-8_58","type":"book-chapter","created":{"date-parts":[[2010,9,22]],"date-time":"2010-09-22T21:14:37Z","timestamp":1285190077000},"page":"742-746","source":"Crossref","is-referenced-by-count":29,"title":["How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails"],"prefix":"10.1007","author":[{"given":"Haixia","family":"Jia","sequence":"first","affiliation":[]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"58_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Beame, P., Molloy, M.: A sharp threshold in proof complexity. In: Proc. 33rd Symp. on Theory of Computing, pp. 337\u2013346","DOI":"10.1145\/380752.380820"},{"key":"58_CR2","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Molloy, M.: Analysis of a list-colouring algorithm on a random graph. In: Proc. 38th Foundations of Computer Science, pp. 204\u2013212","DOI":"10.1109\/SFCS.1997.646109"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Moore, C.: Almost all graphs of degree 4 are 3-colorable. In: Proc. 34th Symp. on Theory of Computing, pp. 199\u2013208, and J. Comp. & Sys. Sci. 67, 441\u2013471 (2003); special issue for STOC 2002.","DOI":"10.1016\/S0022-0000(03)00120-X"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Chen, H., Gomes, C.P., Selman, B.: Formal models of heavy-tailed behavior in combinatorial search. In: Proc. 7th Intl. Conf. on the Principles and Practice of Constraint Programming, pp. 408\u2013422 (2001)","DOI":"10.1007\/3-540-45578-7_28"},{"key":"58_CR5","unstructured":"A. Davenport and E.P.K. Tsang, \u201cAn empirical investigation into the exceptionally hard problems.\u201d Proc. Workshop on Constraint-based Reasoning 46\u201353"},{"key":"58_CR6","unstructured":"Deroulers, C., Monasson, R.: Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class. Preprint, condmat\/ 0405319"},{"key":"58_CR7","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0004-3702(94)90109-0","volume":"70","author":"I. Gent","year":"1993","unstructured":"Gent, I., Walsh, T.: Easy problems are sometimes hard. Artificial Intelligence\u00a070, 335\u2013345 (1993)","journal-title":"Artificial Intelligence"},{"key":"58_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BFb0017434","volume-title":"Principles and Practice of Constraint Programming - CP97","author":"C.P. Gomes","year":"1997","unstructured":"Gomes, C.P., Selman, B., Crato, N.: Heavy-Tailed Distributions in Combinatorial Search. In: Smolka, G. (ed.) CP 1997. LNCS, vol.\u00a01330, pp. 121\u2013135. Springer, Heidelberg (1997)"},{"key":"58_CR9","unstructured":"Gomes, C.P., Selman, B., Kautz, H.A.: Boosting Combinatorial Search Through Randomization. In: Proc. 15th Natl. Conf. on Artificial Intelligence, pp. 431\u2013437 (1998)"},{"issue":"1-2","key":"58_CR10","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","volume":"69","author":"T. Hogg","year":"1994","unstructured":"Hogg, T., Williams, C.P.: The Hardest Constraint Problems: A Double Phase Transition. Artificial Intelligence\u00a069(1-2), 359\u2013377 (1994)","journal-title":"Artificial Intelligence"},{"key":"58_CR11","doi-asserted-by":"crossref","unstructured":"Luby, M., Sinclair, A., Zuckerman, D.: Optimal speedup of las vegas algorithms. Information Processing Letters, 173\u2013180 (1993)","DOI":"10.1016\/0020-0190(93)90029-9"},{"key":"58_CR12","doi-asserted-by":"crossref","unstructured":"Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. In: Johnson, D., Trick, M. (eds.). DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a026, pp. 521\u2013532 (1993)","DOI":"10.1090\/dimacs\/026\/25"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2013 CP 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30201-8_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T00:23:00Z","timestamp":1740529380000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30201-8_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540232414","9783540302018"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30201-8_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}