{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:08:32Z","timestamp":1761620912461},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2005,10,1]],"date-time":"2005-10-01T00:00:00Z","timestamp":1128124800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2005,10]]},"DOI":"10.1007\/s10601-005-2807-z","type":"journal-article","created":{"date-parts":[[2005,10,20]],"date-time":"2005-10-20T14:51:44Z","timestamp":1129819904000},"page":"317-337","source":"Crossref","is-referenced-by-count":17,"title":["Statistical Regimes Across Constrainedness Regions"],"prefix":"10.1007","volume":"10","author":[{"given":"Carla P.","family":"Gomes","sequence":"first","affiliation":[]},{"given":"C\u00e8sar","family":"Fern\u00e1ndez","sequence":"additional","affiliation":[]},{"given":"Bart","family":"Selman","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Bessi\u00e8re","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2807_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M., & Stamatiou Y. (1997). Random constraint satisfaction: a more accurate picture. In Proceedings CP'97, Linz, Austria, pages 107\u2013120.","DOI":"10.1007\/BFb0017433"},{"key":"2807_CR2","unstructured":"Bayardo, R., & Miranker, D. (1996). A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), pages 558\u2013562. Portland, OR."},{"key":"2807_CR3","unstructured":"Berre, D. L., & Simon, L. (2004). Fifty-five solvers in Vancouver: The sat 2004 competition. In Proceedings of SAT'04."},{"key":"2807_CR4","doi-asserted-by":"crossref","unstructured":"Bessi\u00e8re, C., & R\u00e9gin, J. (1996). MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems. In Proceedings CP'96, Cambridge, MA, pages 61\u201375.","DOI":"10.1007\/3-540-61551-2_66"},{"key":"2807_CR5","unstructured":"Bessi\u00e8re, C., Zanuttini, B., & Fern\u00e1ndez, C. (2004). Measuring search trees. In B. Hnich (ed.) Proceedings ECAI'04 Workshop on Modelling and Solving Problems with Constraints, Valencia, Spain."},{"key":"2807_CR6","doi-asserted-by":"crossref","unstructured":"Chen, H., Gomes, C., & Selman, B. (2001). Formal models of heavy-tailed behavior in combinatorial search. In Proceedings CP'01, Paphos, Cyprus, pages 408\u2013421.","DOI":"10.1007\/3-540-45578-7_28"},{"issue":"3","key":"2807_CR7","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","volume":"41","author":"R. Dechter","year":"1990","unstructured":"Dechter, R. (1990). Enhancement schemes for constraint processing: Back-jumping, learning and cutset decomposition. Artif. Intell. 41(3): 273\u2013312.","journal-title":"Artif. Intell."},{"key":"2807_CR8","unstructured":"Dechter, R. (2003). Constraint processing. Morgan Kaufmann."},{"key":"2807_CR9","first-page":"327","volume-title":"AAAI-97","author":"D. Frost","year":"1997","unstructured":"Frost, D., Rish, I., & Vila, L. (1997). Summarizing CSP hardness with continuous probability distributions. In AAAI-97, Providence, Rhode Island, pages 327\u2013333."},{"key":"2807_CR10","unstructured":"Gaschnig, J. (1977). A general backtrack algorithm that eliminates most redundant tests. In Proceedings IJCAI'77, Cambridge, MA, page 447."},{"key":"2807_CR11","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0004-3702(94)90109-0","volume":"70","author":"I. Gent","year":"1994","unstructured":"Gent, I., & Walsh, T. (1994). Easy problems are sometimes hard. Artif. Intell. 70: 335\u2013345.","journal-title":"Artif. Intell."},{"key":"2807_CR12","doi-asserted-by":"crossref","unstructured":"Gomes, C., Selman, B., & Crato, N. (1997). Heavy-tailed distributions in combinatorial search. In Proceedings CP'97, Linz, Austria, pages 121\u2013135.","DOI":"10.1007\/BFb0017434"},{"issue":"1\u20132","key":"2807_CR13","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1023\/A:1006314320276","volume":"24","author":"C. P. Gomes","year":"2000","unstructured":"Gomes, C. P., Selman, B., Crato, N., & Kautz, H. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. J. Autom. Reason. 24(1\u20132): 67\u2013100.","journal-title":"J. Autom. Reason."},{"key":"2807_CR14","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0004-3702(80)90051-X","volume":"14","author":"R. Haralick","year":"1980","unstructured":"Haralick, R., & Elliot, G. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artif. Intell. 14: 263\u2013313.","journal-title":"Artif. Intell."},{"issue":"1\u20132","key":"2807_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(95)00044-5","volume":"81","author":"T. Hogg","year":"1996","unstructured":"Hogg, T., Huberman, B., & Williams, C. (1996). Phase transitions and search problems. Artif. Intell. 81(1\u20132): 1\u201315.","journal-title":"Artif. Intell."},{"key":"2807_CR16","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","volume":"69","author":"T. Hogg","year":"1994","unstructured":"Hogg, T., & Williams, C. (1994). The hardest constraint problems: A double phase transition. Artif. Intell. 69: 359\u2013377.","journal-title":"Artif. Intell."},{"key":"2807_CR17","unstructured":"Hoos, H. H., & St\u00fctzle, T. (2004). Stochastic Local Search: Foundations and Applications. Morgan Kaufmann."},{"key":"2807_CR18","unstructured":"Horvitz, E., Ruan, Y., Gomes, C., Kautz, H., Selman, B., & Chickering, M. (2001). A Bayesian approach to tackling hard computational problems. In Proceedings of the Seventeenth Conference On Uncertainty in Artificial Intelligence (UAI-01)."},{"key":"2807_CR19","unstructured":"Kautz, H., Horvitz, E., Ruan, Y., Gomes, C., & Selman, B. (2002). Dynamic restart policies. In Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), Edmonton, Canada."},{"key":"2807_CR20","unstructured":"Li, C., & Ambulagan. (1997). Heuristics based on unit propagation for satisfiability problems. In Proceedings IJCAI'97, Nagoya, Japan. pages 366\u2013371."},{"issue":"5","key":"2807_CR21","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1109\/12.769433","volume":"48","author":"J. P. Marques-Silva","year":"1999","unstructured":"Marques-Silva, J. P., & Sakallah, K. A. (1999). GRASP\u2014A search algorithm for propositional satisfiability. IEEE Trans. Comput. 48(5): 506\u2013521.","journal-title":"IEEE Trans. Comput."},{"key":"2807_CR22","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0004-3702(86)90083-4","volume":"28","author":"R. Mohr","year":"1986","unstructured":"Mohr, R., & Henderson, T. (1986). Arc and path consistency revisited. Artif. Intell. 28: 225\u2013233.","journal-title":"Artif. Intell."},{"key":"2807_CR23","doi-asserted-by":"crossref","unstructured":"Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., & Malik, S. (2001). Chaff: Engineering an efficient SAT solver. In Proceedings of the 39th Design Automation Conference, Las Vegas.","DOI":"10.1145\/378239.379017"},{"key":"2807_CR24","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1111\/j.1467-8640.1989.tb00328.x","volume":"5","author":"B. Nadel","year":"1989","unstructured":"Nadel, B. (1989) Constraint satisfaction algorithms. Comput. Intell. 5: 188\u2013224.","journal-title":"Comput. Intell."},{"key":"2807_CR25","unstructured":"Prosser, P. (1993a). Domain filtering can degrade intelligent backtrack search. In Proceedings IJCAI'93, Chambry, France, pages 262\u2013267."},{"issue":"3","key":"2807_CR26","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1111\/j.1467-8640.1993.tb00310.x","volume":"9","author":"P. Prosser","year":"1993","unstructured":"Prosser, P. (1993b), Hybrid algorithms for the constraint satisfaction problem. Comput. Intell. 9(3): 268\u2013299.","journal-title":"Comput. Intell."},{"issue":"1\/2","key":"2807_CR27","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1023\/A:1006303512524","volume":"24","author":"I. Rish","year":"2000","unstructured":"Rish, I., & Dechter, R. (2000). Resolution versus Search: Two strategies for SAT'. J. Autom. Reason. 24(1\/2): 225\u2013275.","journal-title":"J. Autom. Reason."},{"key":"2807_CR28","doi-asserted-by":"crossref","unstructured":"Sabin, D., & Freuder, E. (1994). Contradicting conventional wisdom in constraint satisfaction. In Proceedings PPCP'94, Seattle WA.","DOI":"10.1007\/3-540-58601-6_86"},{"issue":"1\u20132","key":"2807_CR29","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(95)00056-9","volume":"81","author":"B. Selman","year":"1996","unstructured":"Selman, B., & Kirkpatrick, S. (1996). Finite-size scaling of the computational cost of systematic search. Artif. Intell. 81(1\u20132): 273\u2013295.","journal-title":"Artif. Intell."},{"key":"2807_CR30","unstructured":"Smith, B., & Grant, S. (1995). Sparse constraint graphs and exceptionally hard problems. In Proceedings IJCAI'95, Montral, Canada, pages 646\u2013651."},{"key":"2807_CR31","doi-asserted-by":"crossref","unstructured":"Smith, B., & Grant, S. (1997). Modelling exceptionally hard constraint satisfaction problems. In Proceedings CP'97, Linz, Austria, pages 182\u2013195.","DOI":"10.1007\/BFb0017439"},{"key":"2807_CR32","doi-asserted-by":"crossref","unstructured":"Walsh, T. (2000) SAT vs CSP. In Proceedings CP'00, pages 441\u2013456. Singapore.","DOI":"10.1007\/3-540-45349-0_32"},{"key":"2807_CR33","unstructured":"Williams, R., Gomes, C., & Selman, B. (2003). Backdoors to Typical Case Complexity."},{"key":"2807_CR34","unstructured":"Williams, R., Gomes, C., & Selman, B. (2003). On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In Proceedings of Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT-03)."},{"key":"2807_CR35","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","volume":"12","author":"K. Xu","year":"2000","unstructured":"Xu, K., & Li, W. (2000). Exact phase transition in random constraint satisfaction problems. J. Artif. Intell. Res. 12: 93\u2013103.","journal-title":"J. Artif. Intell. Res."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-005-2807-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-005-2807-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-005-2807-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T11:22:31Z","timestamp":1586517751000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-005-2807-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,10]]}},"alternative-id":["2807"],"URL":"https:\/\/doi.org\/10.1007\/s10601-005-2807-z","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}