{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,14]],"date-time":"2025-07-14T02:49:01Z","timestamp":1752461341944},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602996"},{"type":"electronic","value":"9783540447887"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60299-2_5","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:16:00Z","timestamp":1330262160000},"page":"70-87","source":"Crossref","is-referenced-by-count":15,"title":["Scaling effects in the CSP phase transition"],"prefix":"10.1007","author":[{"given":"Ian P.","family":"Gent","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ewan","family":"MacIntyre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"Prosser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toby","family":"Walsh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"5_CR1","unstructured":"M.N. Barber. Finite-size scaling. In Phase Transitions and Critical Phenomena, Volume 8, pages 145\u2013266. Academic Press, 1983."},{"key":"5_CR2","unstructured":"P. Cheeseman, B. Kanefsky, and W.M. Taylor. Where the really hard problems are. In Proceedings of the 12th IJCAI, pages 331\u2013337. International Joint Conference on Artificial Intelligence, 1991."},{"key":"5_CR3","first-page":"276","volume-title":"Encyclopedia of Artificial Intelligence","author":"R. Dechter","year":"1992","unstructured":"R. Dechter, Constraint Networks, in Encyclopedia of Artificial Intelligence, Wiley, New York, 2nd ed., 276\u2013286, 1992.","edition":"2nd ed."},{"issue":"2","key":"5_CR4","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0004-3702(94)90068-X","volume":"68","author":"R. Dechter","year":"1994","unstructured":"R. Dechter and I. Meiri, Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Artif. Intell.\n68(2) (1994) 211\u2013242.","journal-title":"Artif. Intell."},{"key":"5_CR5","unstructured":"D. Frost and R. Dechter, In search of the best search: an empirical evaluation, Proceedings AAAI-94, Seattle, WA (1994) 301\u2013306."},{"key":"5_CR6","unstructured":"J. Gaschnig, A general backtracking algorithm that eliminates most redundant tests, Proceedings IJCAI-77, Cambridge, MA (1977) 457."},{"key":"5_CR7","volume-title":"Tech. Rept. CMU-CS-79-124","author":"J. Gaschnig","year":"1979","unstructured":"J. Gaschnig, Performance measurement and analysis of certain search algorithms, Tech. Rept. CMU-CS-79-124, Carnegie-Mellon University, Pittsburgh, PA (1979)."},{"key":"5_CR8","unstructured":"I. P. Gent and T. Walsh. The SAT phase transition. In Proceedings of ECAI-94, pages 105\u2013109, 1994."},{"key":"5_CR9","unstructured":"I.P. Gent and T. Walsh. The satisfiability constraint gap. To appear in Artificial Intelligence."},{"key":"5_CR10","series-title":"Research report 95-178","volume-title":"The TSP phase transition","author":"I.P. Gent","year":"1995","unstructured":"I.P. Gent and T. Walsh. The TSP phase transition. Research report 95-178, Department of Computer Science, University of Strathclyde, 1995. Presented at First Workshop on AI and OR, Timberline, Oregon."},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1145\/321296.321300","volume":"12","author":"S.W. Golomb","year":"1965","unstructured":"S.W. Golomb and L.D. Baumert, Backtrack programming. JACM\n12 (1965) 516\u2013524.","journal-title":"JACM"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0004-3702(80)90051-X","volume":"14","author":"R.M. Haralick","year":"1980","unstructured":"R.M. Haralick and G.L. Elliott, Increasing Tree Search Efficiency for Constraint Satisfaction Problems, Artif. Intell.\n14 (1980) 263\u2013313.","journal-title":"Artif. Intell."},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","volume":"69","author":"T. Hogg","year":"1994","unstructured":"T. Hogg and C. Williams. The hardest constraint problems: A double phase transition. Artificial Intelligence, 69:359\u2013377, 1994.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"5_CR14","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1287\/opre.42.2.201","volume":"42","author":"J.N. Hooker","year":"1994","unstructured":"J.N. Hooker, Needed: An empirical science of algorithms, Operations Research\n42 (2) (1994) 201\u2013212.","journal-title":"Operations Research"},{"key":"5_CR15","unstructured":"S. Kirkpatrick, G. Gy\u00f6rgyi, N. Tishby, and L. Troyansky. The statistical mechanics of k-satisfaction. In Advances in Neural Information Processing Systems 6, pages 439\u2013446. Morgan Kaufmann, 1994."},{"key":"5_CR16","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S. Kirkpatrick","year":"1994","unstructured":"S. Kirkpatrick and B. Selman. Critical behavior in the satisfiability of random boolean expressions. Science, 264:1297\u20131301, May 27 1994.","journal-title":"Science"},{"issue":"1","key":"5_CR17","first-page":"32","volume":"13","author":"V. Kumar","year":"1992","unstructured":"V. Kumar, Algorithms for constraint satisfaction problems: a survey, AI magazine 13(1) (1992) 32\u201344.","journal-title":"AI magazine"},{"key":"5_CR18","volume-title":"Final Year Report for the B.Sc. degree","author":"E. MacIntyre","year":"1994","unstructured":"E. MacIntyre, Really hard problems, Final Year Report for the B.Sc. degree, Department of Computer Science, University of Strathclyde, Scotland, 1994."},{"key":"5_CR19","unstructured":"D. Mitchell, B. Selman, and Hector Levesque. Hard and easy distributions of SAT problems. In Proceedings, 10th National Conference on Artificial Intelligence. AAAI Press\/The MIT Press, pages 459\u2013465, 1992."},{"key":"5_CR20","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1111\/j.1467-8640.1993.tb00310.x","volume":"9","author":"P. Prosser","year":"1993","unstructured":"P. Prosser. Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence, 9:268\u2013299, 1993.","journal-title":"Computational Intelligence"},{"key":"5_CR21","unstructured":"P. Prosser. Binary constraint satisfaction problems: Some are harder than others. In Proceedings of ECAI-94, pages 95\u201399, 1994."},{"key":"5_CR22","unstructured":"P. Prosser. An empirical study of phase transitions in binary constraint satisfaction problems. To appear in Artificial Intelligence."},{"key":"5_CR23","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0004-3702(83)80007-1","volume":"21","author":"P.W. Purdom","year":"1983","unstructured":"P.W. Purdom, Search rearrangement backtracking and polynomial average time, Artif. Intell.\n21 (1983) 117\u2013133.","journal-title":"Artif. Intell."},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"D. Sabin and E.C. Freuder, Contradicting conventional wisdom in constraint satisfaction, Proceedings ECAI-94, Amsterdam, The Netherlands (1994) 125\u2013129.","DOI":"10.1007\/3-540-58601-6_86"},{"key":"5_CR25","unstructured":"B. Selman and S. Kirkpatrick. Critical behaviour in the computational cost of satisfiability testing. To appear in Artificial Intelligence."},{"key":"5_CR26","unstructured":"B.M Smith. Phase transition and the mushy region in constraint satisfaction problems. In Proceedings of ECAI-94, pages 100\u2013104, 1994."},{"key":"5_CR27","unstructured":"B. M. Smith and M.E. Dyer. Locating the phase transition in binary constraint satisfaction problems. To appear in Artificial Intelligence."},{"key":"5_CR28","unstructured":"E.P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993."},{"key":"5_CR29","first-page":"203","volume-title":"Proceedings AISB-95","author":"E.P.K. Tsang","year":"1995","unstructured":"E.P.K. Tsang, J. Borrett, and A.C.M. Kwan, An attempt to map the performance of a range of algorithm and heuristic combinations, In Proceedings AISB-95, pages 203\u2013216, Ed. J. Hallam, IOS Press, Amsterdam, 1995."},{"key":"5_CR30","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","volume":"70","author":"C.P. Williams","year":"1994","unstructured":"C.P. Williams and T. Hogg. Exploiting the deep structure of constraint problems. Artificial Intelligence, 70:73\u2013117, 1994.","journal-title":"Artificial Intelligence"},{"key":"5_CR31","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1038\/scientificamerican0879-158","volume":"241","author":"K.G. Wilson","year":"1979","unstructured":"K.G. Wilson. Problems in physics with many scales of length. Scientific American, 241:140\u2013157, 1979.","journal-title":"Scientific American"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2014 CP '95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60299-2_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:36:58Z","timestamp":1619559418000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60299-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602996","9783540447887"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-60299-2_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}