{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:54Z","timestamp":1760202714020,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L021226\/1"],"award-info":[{"award-number":["EP\/L021226\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s10601-016-9251-0","type":"journal-article","created":{"date-parts":[[2016,8,23]],"date-time":"2016-08-23T02:59:15Z","timestamp":1471921155000},"page":"3-23","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The power of propagation: when GAC is enough"],"prefix":"10.1007","volume":"22","author":[{"given":"David A.","family":"Cohen","sequence":"first","affiliation":[]},{"given":"Peter G.","family":"Jeavons","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,23]]},"reference":[{"key":"9251_CR1","doi-asserted-by":"crossref","unstructured":"Aschinger, M., Drescher, C., Friedrich, G., Gottlob, G., Jeavons, P., Ryabokon, A., & Thorstensen, E. (2011). Optimization methods for the partner units problem. In Proceedings of (CPAIOR\u201911). Lecture Notes in Computer Science, vol. 6697, pp. 4\u201319. Springer.","DOI":"10.1007\/978-3-642-21311-3_4"},{"key":"9251_CR2","doi-asserted-by":"crossref","unstructured":"Bacchus, F. (2007). GAC via unit propagation. In Principles and Practice of Constraint Programming - CP 2007. Lecture Notes in Computer Science, vol. 4741, pp. 133\u2013147. Springer.","DOI":"10.1007\/978-3-540-74970-7_12"},{"key":"9251_CR3","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C Beeri","year":"1983","unstructured":"Beeri, C., Fagin, R., Maier, D., & Yannakakis, M. (1983). On the desirability of acyclic database schemes. Journal of the ACM, 30, 479\u2013513.","journal-title":"Journal of the ACM"},{"issue":"1","key":"9251_CR4","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10601-006-9010-8","volume":"12","author":"N Beldiceanu","year":"2007","unstructured":"Beldiceanu, N., Carlsson, M., Demassey, S., & Petit, T. (2007). Global constraint catalogue: Past, present and future. Constraints, 12(1), 21\u201362.","journal-title":"Constraints"},{"key":"9251_CR5","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s10601-006-9007-3","volume":"12","author":"C Bessiere","year":"2007","unstructured":"Bessiere, C., Hebrard, E., Hnich, B., & Walsh, T. (2007). The complexity of reasoning with global constraints. Constraints, 12, 239\u2013259.","journal-title":"Constraints"},{"key":"9251_CR6","unstructured":"Bessiere, C., Katsirelos, G., Narodytska, N., Quimper, C., & Walsh, T. (2009). Decompositions of all different, global cardinality and related constraints. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence. pp. 419\u2013424."},{"key":"9251_CR7","doi-asserted-by":"crossref","unstructured":"Bessiere, C., Katsirelos, G., Narodytska, N., Quimper, C., & Walsh, T. (2010). Propagating conjunctions of alldifferent constraints. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010.","DOI":"10.1609\/aaai.v24i1.7554"},{"key":"9251_CR8","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., & Krokhin, A. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34, 720\u2013742.","journal-title":"SIAM Journal on Computing"},{"key":"9251_CR9","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., & Jeavons, P. (2003). An algebraic approach to multi-sorted constraints. In Principles and Practice of Constraint Programming - CP 2003. Lecture Notes in Computer Science, vol. 2833, pp. 183\u2013198. Springer.","DOI":"10.1007\/978-3-540-45193-8_13"},{"key":"9251_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-6(4:4)2010","volume":"6","author":"AA Bulatov","year":"2010","unstructured":"Bulatov, A.A., & Marx, D. (2010). The complexity of global cardinality constraints. Logical Methods in Computer Science, 6, 1\u201327.","journal-title":"Logical Methods in Computer Science"},{"key":"9251_CR11","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1016\/j.jcss.2010.04.003","volume":"76","author":"H Chen","year":"2010","unstructured":"Chen, H., & Grohe, M. (2010). Constraint satisfaction with succinctly specified relations. Journal of Computer and System Sciences, 76, 847\u2013860.","journal-title":"Journal of Computer and System Sciences"},{"key":"9251_CR12","doi-asserted-by":"crossref","unstructured":"Cohen, D.A. (2003). A new classs of binary CSPs for which arc-constistency is a decision procedure. In Principles and Practice of Constraint Programming - CP 2003. Lecture Notes in Computer Science, vol. 2833, pp. 807\u2013811. Springer.","DOI":"10.1007\/978-3-540-45193-8_57"},{"key":"9251_CR13","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1023\/B:CONS.0000036045.82829.94","volume":"9","author":"DA Cohen","year":"2004","unstructured":"Cohen, D.A. (2004). Tractable decision for a constraint language implies tractable search. Constraints, 9, 219\u2013229.","journal-title":"Constraints"},{"issue":"5","key":"9251_CR14","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1016\/j.jcss.2007.08.001","volume":"74","author":"DA Cohen","year":"2008","unstructured":"Cohen, D.A., Jeavons, P., & Gyssens, M. (2008). A unified theory of structural tractability for constraint satisfaction problems. Journal of Computer and System Sciences, 74(5), 721\u2013743.","journal-title":"Journal of Computer and System Sciences"},{"key":"9251_CR15","doi-asserted-by":"crossref","unstructured":"Cohen, D.A., Jeavons, P.G., Thorstensen, E., & \u017eivn\u00fd, S. (2013). Tractable combinations of global constraints. In Principles and Practice of Constraint Programming CP 2013. Lecture Notes in Computer Science, vol. 8124, pp. 230\u2013246. Springer.","DOI":"10.1007\/978-3-642-40627-0_20"},{"key":"9251_CR16","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(84)90075-1","volume":"8","author":"CJ Colbourn","year":"1984","unstructured":"Colbourn, C.J. (1984). The complexity of completing partial Latin squares. Discrete Applied Mathematics, 8, 25\u201330.","journal-title":"Discrete Applied Mathematics"},{"key":"9251_CR17","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.artint.2016.02.001","volume":"234","author":"MC Cooper","year":"2016","unstructured":"Cooper, M.C., Duchein, A., Mouelhi, A.E., Escamocher, G., Terrioux, C., & Zanuttini, B. (2016). Broken triangles: From value merging to a tractable class of general-arity constraint satisfaction problems. Artificial Intelligence, 234, 196\u2013218.","journal-title":"Artificial Intelligence"},{"issue":"9-10","key":"9251_CR18","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1016\/j.artint.2010.03.002","volume":"174","author":"MC Cooper","year":"2010","unstructured":"Cooper, M.C., Jeavons, P.G., & Salamon, A.Z. (2010). Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination. Artificial Intelligence, 174(9-10), 570\u2013584.","journal-title":"Artificial Intelligence"},{"key":"9251_CR19","doi-asserted-by":"crossref","unstructured":"Cooper, M.C., & \u017eivn\u00fd, S. (2016). The power of arc consistency for CSPs defined by partially-ordered forbidden patterns. In Proceedings of the 31st Annual ACM\/IEE Symposium on Logic in Computer Science (LICS16). p. to appear.","DOI":"10.1145\/2933575.2933587"},{"key":"9251_CR20","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Kolaitis, P.G., & Vardi, M.Y. (2002). Constraint satisfaction, bounded treewidth, and finite-variable logics. In Principles and Practice of Constraint Programming (CP\u201902). Lecture Notes in Computer Science, vol. 2470, pp. 223\u2013254. Springer.","DOI":"10.1007\/3-540-46135-3_21"},{"key":"9251_CR21","doi-asserted-by":"crossref","unstructured":"Dalmau, V., & Pearson, J. (1999). Closure functions and width 1 problems. In Principles and Practice of Constraint Programming - CP\u201999. Lecture Notes in Computer Science, vol. 1713, pp. 159\u2013173. Springer.","DOI":"10.1007\/978-3-540-48085-3_12"},{"key":"9251_CR22","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R Dechter","year":"1989","unstructured":"Dechter, R., & Pearl, J. (1989). Tree clustering for constraint networks. Artificial Intelligence, 38, 353\u2013366.","journal-title":"Artificial Intelligence"},{"key":"9251_CR23","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., & Vardi, M.Y. (1998). The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing, 28, 57\u2013104.","journal-title":"SIAM Journal on Computing"},{"key":"9251_CR24","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.tcs.2012.11.038","volume":"472","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Friedrich, T., Hermelin, D., Narodytska, N., & Rosamond, F.A. (2013). Constraint satisfaction problems: Convexity makes alldifferent constraints tractable. Theoretical Computer Science, 472, 81\u201389.","journal-title":"Theoretical Computer Science"},{"key":"9251_CR25","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"EC Freuder","year":"1982","unstructured":"Freuder, E.C. (1982). A sufficient condition for backtrack-free search. Journal of the ACM, 29, 24\u201332.","journal-title":"Journal of the ACM"},{"key":"9251_CR26","unstructured":"Freuder, E.C. (1990). Complexity of k-tree structured constraint satisfaction problems. In Proceedings of the 8th National Conference on Artificial Intelligence. pp. 4\u20139. AAAI Press \/ The MIT Press."},{"key":"9251_CR27","unstructured":"Gomes, C.P., & Shmoys, D.B. (2002). The promise of LP to boost CSP techniques for combinatorial problems. Proceedings (CP-AI-OR02), 25\u201327."},{"key":"9251_CR28","doi-asserted-by":"crossref","first-page":"2000","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., & Scarcello, F. (2000). A comparison of structural CSP decomposition methods. Artificial Intelligence, 124, 2000.","journal-title":"Artificial Intelligence"},{"key":"9251_CR29","doi-asserted-by":"crossref","unstructured":"Green, M.J., & Cohen, D.A. (2003). Tractability by approximating constraint languages. In Principles and Practice of Constraint Programming - CP 2003. Lecture Notes in Computer Science, vol. 2833, pp. 392\u2013406. Springer.","DOI":"10.1007\/978-3-540-45193-8_27"},{"key":"9251_CR30","doi-asserted-by":"crossref","unstructured":"Green, M.J., & Jefferson, C. (2008). Structural tractability of propagated constraints. In Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP\u201908). Lecture Notes in Computer Science, vol. 5202, pp. 372\u2013386. Springer.","DOI":"10.1007\/978-3-540-85958-1_25"},{"key":"9251_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M. (2007). The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54, 1\u201324.","journal-title":"Journal of the ACM"},{"key":"9251_CR32","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","volume":"66","author":"M Gyssens","year":"1994","unstructured":"Gyssens, M., Jeavons, P.G., & Cohen, D.A. (1994). Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence, 66, 57\u201389.","journal-title":"Artificial Intelligence"},{"key":"9251_CR33","doi-asserted-by":"crossref","unstructured":"Hermenier, F., Demassey, S., & Lorca, X. (2011). Bin repacking scheduling in virtualized datacenters. In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP\u201911). Lecture Notes in Computer Science, vol. 6876, pp. 27\u201341. Springer.","DOI":"10.1007\/978-3-642-23786-7_5"},{"key":"9251_CR34","doi-asserted-by":"crossref","unstructured":"van Hoeve, W.J., & Katriel, I. (2006). Global constraints. In Rossi, F., van Beek, P., & Walsh, T. (Eds.) Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2, chap. 6, pp. 169\u2013208. Elsevier.","DOI":"10.1016\/S1574-6526(06)80010-6"},{"key":"9251_CR35","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D.A., & Gyssens, M. (1997). Closure properties of constraints. Journal of the ACM, 44, 527\u2013548.","journal-title":"Journal of the ACM"},{"key":"9251_CR36","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"P Jeavons","year":"1995","unstructured":"Jeavons, P., & Cooper, M.C. (1995). Tractable constraints on ordered domains. Artificial Intelligence, 79, 327\u2013339.","journal-title":"Artificial Intelligence"},{"key":"9251_CR37","doi-asserted-by":"crossref","unstructured":"Kumar, T.K.S. (2008). A framework for hybrid tractability results in boolean weighted constraint satisfaction problems. In Principles and Practice of Constraint Programming CP 2008. Lecture Notes in Computer Science, vol. 5202, pp. 282\u2013297. Springer.","DOI":"10.1007\/978-3-540-85958-1_19"},{"key":"9251_CR38","doi-asserted-by":"crossref","unstructured":"Marx, D. (2010). Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In Proceedings of the 42nd ACM Symposium on Theory of Computing, (STOC\u201910). pp. 735\u2013744. ACM.","DOI":"10.1145\/1806689.1806790"},{"key":"9251_CR39","unstructured":"Pesant, G. CSPLib problem 067: Quasigroup completion. http:\/\/www.csplib.org\/Problems\/prob067 ."},{"key":"9251_CR40","unstructured":"R\u00e9gin, J.C. (1996). Generalized Arc Consistency for Global Cardinality Constraint. In Proceedings of the 13th National Conference on AI (AAAI\u201996). vol. 1, pp. 209\u2013215."},{"key":"9251_CR41","unstructured":"Rossi, F., van Beek, P., & Walsh, T. (Eds.) (2006). The Handbook of Constraint Programming: Elsevier."},{"key":"9251_CR42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10601-009-9079-y","volume":"16","author":"M Samer","year":"2011","unstructured":"Samer, M., & Szeider, S. (2011). Tractable cases of the extended global cardinality constraint. Constraints, 16, 1\u201324.","journal-title":"Constraints"},{"key":"9251_CR43","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF00143881","volume":"1","author":"M Wallace","year":"1996","unstructured":"Wallace, M. (1996). Practical applications of constraint programming. Constraints, 1, 139\u2013168.","journal-title":"Constraints"},{"key":"9251_CR44","first-page":"137","volume":"12","author":"M Wallace","year":"1997","unstructured":"Wallace, M., Novello, S., & Schimpf, J. (1997). ECLiPSe: A platform for constraint logic programming. ICL Systems Journal, 12, 137\u2013158.","journal-title":"ICL Systems Journal"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9251-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9251-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T20:13:45Z","timestamp":1692476025000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-016-9251-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,23]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["9251"],"URL":"https:\/\/doi.org\/10.1007\/s10601-016-9251-0","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2016,8,23]]}}}