{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T23:40:59Z","timestamp":1769816459716,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540615514","type":"print"},{"value":"9783540706205","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61551-2_74","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:55:47Z","timestamp":1330293347000},"page":"179-193","source":"Crossref","is-referenced-by-count":59,"title":["An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem"],"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":"Presser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barbara M.","family":"Smith","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":[{"issue":"4","key":"13_CR1","first-page":"251","volume":"22","author":"D. Brelaz","year":"1979","unstructured":"D. Brelaz. New methods to color the vertices of a graph. JACM, 22(4):251\u2013256, 1979.","journal-title":"JACM"},{"key":"13_CR2","unstructured":"P. Cheeseman, B. Kanefsky, and W.M. Taylor. Where the really hard problems are. In Proc. IJCAI-91, pages 331\u2013337, 1991."},{"key":"13_CR3","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. Artificial Intelligence, 68:211\u2013241, 1994.","journal-title":"Artificial Intelligence"},{"key":"13_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF01531070","volume":"1","author":"R. Feldman","year":"1990","unstructured":"R. Feldman and M.C. Golumbic. Interactive scheduling as a constraint satisfaction problem. Annals of Mathematics and Artificial Intelligence, 1:49\u201373, 1990.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"13_CR5","unstructured":"J. Gaschnig. A general backtracking algorithm that eliminates most redundant tests. In Proc. IJCAI-77, page 457, 1977."},{"key":"13_CR6","unstructured":"J. Gaschnig. Performance measurement and analysis of certain search algorithms. Tech. rep. CMU-CS-79-124, Carnegie-Mellon University, 1979."},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"I.P. Gent, E. MacIntyre, P. Prosser, and T. Walsh. Scaling effects in the CSP phase transition. In Principles and Practice of Constraint Programming, pages 70\u201387. Springer, 1995.","DOI":"10.1007\/3-540-60299-2_5"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"I.P. Gent, E. MacIntyre, P. Prosser, and T. Walsh. The constrainedness of search. In Proc. AAAI-96, 1996.","DOI":"10.1007\/BFb0017449"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0004-3702(94)90109-0","volume":"70","author":"I.P. Gent","year":"1994","unstructured":"I.P. Gent and T. Walsh. Easy problems are sometimes hard. Artificial Intelligence, 70:335\u2013345, 1994.","journal-title":"Artificial Intelligence"},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1613\/jair.1","volume":"1","author":"M.L. Ginsberg","year":"1993","unstructured":"M.L. Ginsberg. Dynamic backtracking. JAIR, 1:25\u201346, 1993.","journal-title":"JAIR"},{"key":"13_CR11","doi-asserted-by":"crossref","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, 12:516\u2013524, 1965.","journal-title":"JACM"},{"key":"13_CR12","unstructured":"S. Grant and B.M. Smith. The phase transition behaviour of maintaining arc consistency. In Proc. ECAI-96, pages 175\u2013179, 1996."},{"key":"13_CR13","doi-asserted-by":"crossref","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. Artificial Intelligence, 14:263\u2013313, 1980.","journal-title":"Artificial Intelligence"},{"key":"13_CR14","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0004-3702(83)80008-3","volume":"21","author":"B. Nudel","year":"1983","unstructured":"B. Nudel. Consistent-labeling problems and their algorithms: Expected-complexities and theory-based heuristics. Artificial Intelligence, 21:135\u2013178, 1983.","journal-title":"Artificial Intelligence"},{"issue":"3","key":"13_CR15","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(3):268\u2013299, 1993.","journal-title":"Computational Intelligence"},{"issue":"1\u20132","key":"13_CR16","first-page":"1","volume":"81","author":"P. Prosser","year":"1996","unstructured":"P. Prosser. An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence, 81(1\u20132):1\u201315, 1996.","journal-title":"Artificial Intelligence"},{"key":"13_CR17","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. Artificial Intelligence, 21:117\u2013133, 1983.","journal-title":"Artificial Intelligence"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"D. Sabin and E.C. Freuder. Contradicting conventional wisdom in constraint satisfaction. In Proc. ECAI-94, pages 125\u2013129, 1994.","DOI":"10.1007\/3-540-58601-6_86"},{"issue":"1\u20132","key":"13_CR19","first-page":"1","volume":"81","author":"B.M. Smith","year":"1996","unstructured":"B.M. Smith and M.E. Dyer. Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 81(1\u20132):1\u201315, 1996.","journal-title":"Artificial Intelligence"},{"key":"13_CR20","unstructured":"B.M. Smith and S. Grant. Sparse constraint graphs and exceptionally hard problems. In Proc. IJCAI-95, pages 646\u2013651, 1995."},{"key":"13_CR21","unstructured":"E.P.K. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993."},{"key":"13_CR22","unstructured":"E.P.K. Tsang, J.E. Borrett, and A.C.M. Kwan. An attempt to map the performance of a range of algorithm and heuristic combinations. In Hybrid Problems, Hybrid Solutions, pages 203\u2013216. IOS Press, 1995. Proceedings of AISB-95."},{"key":"13_CR23","doi-asserted-by":"crossref","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"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2014 CP96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61551-2_74.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:21:33Z","timestamp":1742599293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61551-2_74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540615514","9783540706205"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-61551-2_74","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}