{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T13:18:50Z","timestamp":1773667130288,"version":"3.50.1"},"reference-count":45,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1996,3,1]],"date-time":"1996-03-01T00:00:00Z","timestamp":825638400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":6355,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[1996,3]]},"DOI":"10.1016\/0004-3702(95)00048-8","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T04:24:09Z","timestamp":1027657449000},"page":"81-109","source":"Crossref","is-referenced-by-count":102,"title":["An empirical study of phase transitions in binary constraint satisfaction problems"],"prefix":"10.1016","volume":"81","author":[{"given":"Patrick","family":"Prosser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0004-3702(95)00048-8_BIB1","author":"Bollob\u00e1s","year":"1985"},{"key":"10.1016\/0004-3702(95)00048-8_BIB2","series-title":"Proceedings IJCAI-91","first-page":"331","article-title":"Where the really hard problems are","author":"Cheeseman","year":"1991"},{"key":"10.1016\/0004-3702(95)00048-8_BIB3","series-title":"Proceedings AAAI-93","first-page":"21","article-title":"Experimental results on the crossover point in satisfiability problems","author":"Crawford","year":"1993"},{"issue":"3","key":"10.1016\/0004-3702(95)00048-8_BIB4","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","article-title":"Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition","volume":"41","author":"Dechter","year":"1990","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00048-8_BIB5","first-page":"276","article-title":"Constraint networks","author":"Dechter","year":"1992"},{"issue":"2","key":"10.1016\/0004-3702(95)00048-8_BIB6","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0004-3702(94)90068-X","article-title":"Experimental evaluation of preprocessing algorithms for constraint satisfaction problems","volume":"68","author":"Dechter","year":"1994","journal-title":"Artif. Intell."},{"issue":"1\u20133","key":"10.1016\/0004-3702(95)00048-8_BIB7","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0004-3702(92)90004-H","article-title":"Partial constraint satisfaction","volume":"58","author":"Freuder","year":"1992","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00048-8_BIB8","series-title":"Proceedings AAAI-94","first-page":"301","article-title":"In search of the best search: an empirical evaluation","author":"Frost","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB9","series-title":"Proceedings AAAI-94","first-page":"294","article-title":"Dead-end driven learning","author":"Frost","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB10","series-title":"Proceedings IJCAI-77","first-page":"457","article-title":"A general backtracking algorithm that eliminates most redundant tests","author":"Gaschnig","year":"1977"},{"key":"10.1016\/0004-3702(95)00048-8_BIB11","article-title":"Performance measurement and analysis of certain search algorithms","author":"Gaschnig","year":"1979"},{"issue":"1\u20132","key":"10.1016\/0004-3702(95)00048-8_BIB12","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0004-3702(94)90109-0","article-title":"Easy problems are sometimes hard","volume":"70","author":"Gent","year":"1994","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00048-8_BIB13","series-title":"Proceedings ECAI-94","first-page":"105","article-title":"The SAT phase transition","author":"Gent","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB14","article-title":"Computational phase transitions in real problems","author":"Gent","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB15","article-title":"The TSP phase transition","author":"Gent","year":"1995"},{"key":"10.1016\/0004-3702(95)00048-8_BIB16","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1613\/jair.1","article-title":"Dynamic backtracking","volume":"1","author":"Ginsberg","year":"1993","journal-title":"J. Artif. Intell. Res."},{"key":"10.1016\/0004-3702(95)00048-8_BIB17","series-title":"Proceedings AAAI-90","first-page":"210","article-title":"Search lessons learned from crossword puzzles","author":"Ginsberg","year":"1990"},{"key":"10.1016\/0004-3702(95)00048-8_BIB18","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1145\/321296.321300","article-title":"Backtrack programming","volume":"12","author":"Colomb","year":"1965","journal-title":"J. ACM"},{"key":"10.1016\/0004-3702(95)00048-8_BIB19","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0004-3702(80)90051-X","article-title":"Increasing tree search efficiency for constraint satisfaction problems","volume":"14","author":"Haralick","year":"1980","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00048-8_BIB20","series-title":"Proceedings IJCAI-93","first-page":"282","article-title":"Exploiting interchangeabilities in constraint satisfaction problems","author":"Haselb\u00f6ck","year":"1993"},{"issue":"1\u20132","key":"10.1016\/0004-3702(95)00048-8_BIB21","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","article-title":"The hardest constraint problems: a double phase transition","volume":"69","author":"Hogg","year":"1994","journal-title":"Artif. Intell."},{"issue":"2","key":"10.1016\/0004-3702(95)00048-8_BIB22","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1287\/opre.42.2.201","article-title":"Needed: An empirical science of algorithms","volume":"42","author":"Hooker","year":"1994","journal-title":"Operations Research"},{"key":"10.1016\/0004-3702(95)00048-8_BIB23","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","article-title":"Critical behavior in the satisfiability of random boolean expressions","volume":"264","author":"Kirkpatrick","year":"1994","journal-title":"Science"},{"issue":"1","key":"10.1016\/0004-3702(95)00048-8_BIB24","first-page":"32","article-title":"Algorithms for constraint satisfaction problems: a survey","volume":"13","author":"Kumar","year":"1992","journal-title":"AI Mag."},{"key":"10.1016\/0004-3702(95)00048-8_BIB25","author":"MacIntyre","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB26","first-page":"285","article-title":"Constraint satisfaction","volume":"Vol. 1","author":"Mackworth","year":"1992"},{"issue":"1","key":"10.1016\/0004-3702(95)00048-8_BIB27","doi-asserted-by":"crossref","first-page":"3","DOI":"10.3233\/AIC-1989-2101","article-title":"Constraint satisfaction problems: an overview","volume":"2","author":"Meseguer","year":"1989","journal-title":"AI Comm."},{"key":"10.1016\/0004-3702(95)00048-8_BIB28","series-title":"Proceedings AAAI-92","first-page":"459","article-title":"Hard and easy distribution of SAT problems","author":"Mitchell","year":"1992"},{"key":"10.1016\/0004-3702(95)00048-8_BIB29","author":"Palmer","year":"1985"},{"issue":"3","key":"10.1016\/0004-3702(95)00048-8_BIB30","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1111\/j.1467-8640.1993.tb00310.x","article-title":"Hybrid algorithms for the constraint satisfaction problem","volume":"9","author":"Prosser","year":"1993","journal-title":"Comput. Intell."},{"key":"10.1016\/0004-3702(95)00048-8_BIB31","series-title":"Proceedings IJCAI-93","first-page":"262","article-title":"Domain filtering can degrade intelligent backtracking search","author":"Prosser","year":"1993"},{"key":"10.1016\/0004-3702(95)00048-8_BIB32","series-title":"Proceedings CAIA-93","first-page":"257","article-title":"BM + BJ = BMJ","author":"Prosser","year":"1993"},{"key":"10.1016\/0004-3702(95)00048-8_BIB33","series-title":"Proceedings ECAI-94","first-page":"95","article-title":"Binary constraint satisfaction problems: some are harder than others","author":"Prosser","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB34","unstructured":"P. Prosser, A csp lab."},{"key":"10.1016\/0004-3702(95)00048-8_BIB35","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0004-3702(83)80007-1","article-title":"Search rearrangement backtracking and polynomial average time","volume":"21","author":"Purdom","year":"1983","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00048-8_BIB36_1","series-title":"Proceedings ECAI-94","first-page":"125","article-title":"Contradicting conventional wisdom in constraint satisfaction","author":"Sabin","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB36_2","series-title":"Proceedings AAAI-92","first-page":"440","author":"Sabin","year":"1992"},{"key":"10.1016\/0004-3702(95)00048-8_BIB37","series-title":"Proceedings ECAI-94","first-page":"100","article-title":"Phase transition and the mushy region in constraint satisfaction problems","author":"Smith","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB38","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","article-title":"Locating the phase transition in binary constraint satisfaction problems","volume":"81","author":"Smith","year":"1996","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00048-8_BIB39","article-title":"Sparse constraint graphs and exceptionally hard problems","author":"Smith","year":"1994"},{"key":"10.1016\/0004-3702(95)00048-8_BIB40","author":"Tsang","year":"1993"},{"key":"10.1016\/0004-3702(95)00048-8_BIB41","series-title":"Proceedings AISB-95","article-title":"An attempt to map the performance of a range of algorithm and heuristic combinations","author":"Tsang","year":"1995"},{"key":"10.1016\/0004-3702(95)00048-8_BIB42","series-title":"Proceedings AAAI-93","article-title":"Extending deep structure","author":"Williams","year":"1993"},{"issue":"3","key":"10.1016\/0004-3702(95)00048-8_BIB43","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1111\/j.1467-8640.1993.tb00307.x","article-title":"The typicality of phase transitions in search","volume":"9","author":"Williams","year":"1993","journal-title":"Comput. Intell."},{"issue":"1\u20132","key":"10.1016\/0004-3702(95)00048-8_BIB44","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","article-title":"Exploiting the deep structure of constraint problems","volume":"70","author":"Williams","year":"1994","journal-title":"Artif. Intell."}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0004370295000488?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0004370295000488?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T15:19:48Z","timestamp":1580915988000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0004370295000488"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,3]]},"references-count":45,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1996,3]]}},"alternative-id":["0004370295000488"],"URL":"https:\/\/doi.org\/10.1016\/0004-3702(95)00048-8","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[1996,3]]}}}