{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,14]],"date-time":"2025-07-14T02:49:15Z","timestamp":1752461355017},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637530"},{"type":"electronic","value":"9783540696421"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0017449","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:22:46Z","timestamp":1132644166000},"page":"327-340","source":"Crossref","is-referenced-by-count":21,"title":["The constrainedness of Arc consistency"],"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":"Paul","family":"Shaw","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,10]]},"reference":[{"key":"25_CR1","unstructured":"Michael N. Barber. Finite-size scaling. In Phase Transitions and Critical Phenomena, Volume 8, pages 145\u2013266. Academic Press, 1983."},{"key":"25_CR2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0004-3702(94)90041-8","volume":"65","author":"C. Bessi\u00e8re","year":"1994","unstructured":"C. Bessi\u00e8re. Arc-consistency and arc-consistency again. Artificial Intelligence, 65:179\u2013190, 1994.","journal-title":"Artificial Intelligence"},{"key":"25_CR3","unstructured":"B. Bollobas. Random Graphs. Academic Press, 1985."},{"key":"25_CR4","unstructured":"P. Cheeseman, B. Kanefsky, and W.M. Taylor. Where the really hard problems are. In Proceedings of IJCAI-91, pages 331\u2013337, 1991."},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"V. Chvatal and B. Reed. Mick gets some (the odds are on his side). In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 620\u2013627. IEEE, 1992.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"25_CR6","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 (CP-95), pages 70\u201387. Springer, 1995.","DOI":"10.1007\/3-540-60299-2_5"},{"key":"25_CR7","unstructured":"I.P. Gent, E. MacIntyre, P. Prosser, and T. Walsh. The constrainedness of search. In Proceedings of AAAI-96, pages 246\u2013252, 1996."},{"key":"25_CR8","unstructured":"I.P. Gent, E. MacIntyre, P. Prosser, and T. Walsh. The scaling of search cost. In Proceedings of AAAI-97, 1997."},{"key":"25_CR9","unstructured":"I.P. Gent and T. Walsh. Phase transitions and annealed theories: Number partitioning as a case study. In Proceedings of ECAI-96, pages 170\u2013174, 1996."},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"S.A. Grant and B.M. Smith. The arc and path consistency phase transitions. Report 96.09, Research Report Series, School of Computer Studies, University of Leeds, March 1996.","DOI":"10.1007\/3-540-61551-2_106"},{"key":"25_CR11","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"},{"key":"25_CR12","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A.K. Mackworth","year":"1977","unstructured":"A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99\u2013118, 1977.","journal-title":"Artificial Intelligence"},{"key":"25_CR13","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0004-3702(85)90041-4","volume":"25","author":"A.K. Mackworth","year":"1985","unstructured":"A.K. Mackworth and E.C. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 25:65\u201374, 1985.","journal-title":"Artificial Intelligence"},{"key":"25_CR14","unstructured":"D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems. In Proceedings of AAAI-92, pages 459\u2013465. AAAI Press\/The MIT Press, 1992."},{"key":"25_CR15","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0004-3702(86)90083-4","volume":"28","author":"R. Mohr","year":"1986","unstructured":"R. Mohr and T.C. Henderson. Arc and path consistency revisited. Artificial Intelligence, 28:225\u2013233, 1986.","journal-title":"Artificial Intelligence"},{"key":"25_CR16","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: Expectedcomplexities and theory-based heuristics. Artificial Intelligence, 21:135\u2013178, 1983.","journal-title":"Artificial Intelligence"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"D. Sabin and E.C. Freuder. Contradicting conventional wisdom in constraint satisfaction. In Proceedings of ECAI-94, pages 125\u2013129, 1994.","DOI":"10.1007\/3-540-58601-6_86"},{"key":"25_CR18","unstructured":"T. Schiex, J-C. R\u00e9gin, C. Gaspin and G. Verfaille. Lazy Arc Consistency. In Proceedings of AAAI-96, pages 216\u2013221, 1996."},{"key":"25_CR19","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(95)00056-9","volume":"81","author":"B. Selman","year":"1996","unstructured":"B. Selman and S. Kirkpatrick. Critical behavior in the computational cost of satisfiability testing. Artificial Intelligence, 81:273\u2013295, 1996.","journal-title":"Artificial Intelligence"},{"key":"25_CR20","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","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:155\u2013181, 1996.","journal-title":"Artificial Intelligence"},{"key":"25_CR21","unstructured":"E.P.K. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993."},{"key":"25_CR22","unstructured":"R.J. Wallace. Why AC-3 is almost always better than AC-4 for establishing arc consistency in CSPs. In Proceedings of IJCAI-93, pages 239\u2013245, 1993."},{"key":"25_CR23","unstructured":"R.J. Wallace and E.C. Freuder. Ordering heuristics for arc consistency algorithms. In Proc. Ninth Canada Conf. on AI, pages 163\u2013169, 1992."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming-CP97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0017449","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T02:53:22Z","timestamp":1586573602000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0017449"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637530","9783540696421"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/bfb0017449","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}