{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:34:30Z","timestamp":1786980870288,"version":"build-2736575974"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,12,2]],"date-time":"2006-12-02T00:00:00Z","timestamp":1165017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2006,12,2]],"date-time":"2006-12-02T00:00:00Z","timestamp":1165017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2007,6]]},"DOI":"10.1007\/s10601-006-9007-3","type":"journal-article","created":{"date-parts":[[2006,12,1]],"date-time":"2006-12-01T14:35:39Z","timestamp":1164983739000},"page":"239-259","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["The Complexity of Reasoning with Global Constraints"],"prefix":"10.1007","volume":"12","author":[{"given":"Christian","family":"Bessiere","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emmanuel","family":"Hebrard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brahim","family":"Hnich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toby","family":"Walsh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,12,2]]},"reference":[{"key":"9007_CR1","doi-asserted-by":"crossref","unstructured":"Beldiceanu, N. (2000). Global Constraints as Graph Properties on a Structured Network of Elementary Constraints of the Same Type. Technical Report, Swedish Institute of Computer Science. SICS Technical Report T2000\/01.","DOI":"10.1007\/3-540-45349-0_6"},{"key":"9007_CR2","first-page":"52","volume-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP\u201900), LNCS 1894, Singapore","author":"N. Beldiceanu","year":"2000","unstructured":"Beldiceanu, N. (2000). Global constraints as graph properties on a structured network of elementary constraints of the same type. In Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP\u201900), LNCS 1894, Singapore, pages 52\u201366. Berlin Heidelberg New York: Springer."},{"key":"9007_CR3","first-page":"211","volume-title":"Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming (CP\u201901), LNCS 2239, Singapore","author":"N. Beldiceanu","year":"2001","unstructured":"Beldiceanu, N. (2001). Pruning for the minimum constraint family and for the number of distinct values constraint family. In Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming (CP\u201901), LNCS 2239, Singapore, pages 211\u2013224. Berlin Heidelberg New York: Springer."},{"key":"9007_CR4","first-page":"59","volume-title":"Proceedings ICLP\u201901","author":"N. Beldiceanu","year":"2001","unstructured":"Beldiceanu, N., & Carlsson, M. (2001). Revisiting the cardinality operator and introducing cardinality-path constraint family. In Proceedings ICLP\u201901, pages 59\u201373. Berlin Heidelberg New York: Springer."},{"issue":"12","key":"9007_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0895-7177(94)90127-9","volume":"20","author":"N. Beldiceanu","year":"1994","unstructured":"Beldiceanu, N., & Contegean, E. (1994). Introducing global constraints in CHIP. Math. Comput. Model. 20(12): 97\u2013123.","journal-title":"Math. Comput. Model."},{"key":"9007_CR6","unstructured":"Bessiere, C. (2005). Complexity of the\n                           cardpath\n                           Constraint. Technical Report TR-05036, LIRMM (CNRS\/University of Montpellier), Montpellier, France, (January)."},{"key":"9007_CR7","doi-asserted-by":"crossref","unstructured":"Bessiere, C., Hebrard, E., Hnich, B., Kiziltan, Z., & Walsh, T. (2005). Filtering algorithms for the NValue constraint. In Proceedings CPAIOR\u201905, Prague, Czech Republic.","DOI":"10.1007\/11493853_8"},{"key":"9007_CR8","unstructured":"Bessiere, C., & R\u00e9gin, J.C. (1997). Arc consistency for general constraint networks: preliminary results. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI\u201997), Nagoya, Japan, pages 398\u2013404."},{"key":"9007_CR9","first-page":"789","volume-title":"Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833. Kinsale, Ireland","author":"C. Bessiere","year":"2003","unstructured":"Bessiere, C., & Van Hentenryck, P. (2003). To be or not to be ... a global constraint. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833. Kinsale, Ireland, pages 789\u2013794. Berlin Heidelberg New York: Springer (Short paper)."},{"key":"9007_CR10","unstructured":"Carlsson, M., & Beldiceanu, N. (2002). Arc-consistency for a Chain of Lexicographic Ordering Constraints. Technical Report T2002-18, Swedish Institute of Computer Science, Sweden. ftp:\/\/ftp.sics.se\/pub\/SICS-reports\/Reports\/SICS-T-2002-18-SE.ps.Z."},{"key":"9007_CR11","first-page":"17","volume-title":"Proceedings of the Third International Conference on Principles and Practice of Constraint Programming (CP\u201997), LNCS 1330. Linz, Austria","author":"Y. Caseau","year":"1997","unstructured":"Caseau, Y., & Laburthe, F. (1997). Solving various weighted matching problems with constraints. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming (CP\u201997), LNCS 1330. Linz, Austria, pages 17\u201331. Berlin Heidelberg New York: Springer."},{"key":"9007_CR12","first-page":"478","volume-title":"Proceedings of the Third International Conference on Principles and Practice of Constraint Programming (CP\u201997), LNCS 1330. Linz, Austria","author":"D.A. Cohen","year":"1997","unstructured":"Cohen, D. A., Jeavons, P., & Koubarakis, M. (1997). Tractable disjunctive constraints. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming (CP\u201997), LNCS 1330. Linz, Austria, pages 478\u2013490. Berlin Heidelberg New York: Springer."},{"key":"9007_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R. Dechter","year":"1988","unstructured":"Dechter, R., & Pearl, J. (1988). Network-based heuristics for constraint-satisfaction problems. Artif. Intell. 34: 1\u201338.","journal-title":"Artif. Intell."},{"key":"9007_CR14","doi-asserted-by":"publisher","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. Artif. Intell. 38: 353\u2013366.","journal-title":"Artif. Intell."},{"key":"9007_CR15","unstructured":"Deville, Y., Barette, O., & Van Hentenryck, P. (1997). Constraint satisfaction over connected row convex constraints. In Proceedings IJCAI\u201997. Nagoya, Japan, pages 405\u2013410."},{"key":"9007_CR16","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1023\/A:1020589922418","volume":"7","author":"F. Focacci","year":"2002","unstructured":"Focacci, F., Lodi, A., & Milano, M. (2002). Optimization-oriented global constraints. Constraints 7: 351\u2013365.","journal-title":"Constraints"},{"issue":"1","key":"9007_CR17","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E.C. Freuder","year":"1982","unstructured":"Freuder, E. C. (1982). A sufficient condition for backtrack-free search. J. ACM 29(1): 24\u201332 (January).","journal-title":"J. ACM"},{"key":"9007_CR18","first-page":"93","volume-title":"Proceedings of the Eight International Conference on Principles and Practice of Constraint Programming (CP\u201902), LNCS 2470. Ithaca, NY","author":"A. Frisch","year":"2002","unstructured":"Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., & Walsh, T. (2002). Global constraints for lexicographic orderings. In Proceedings of the Eight International Conference on Principles and Practice of Constraint Programming (CP\u201902), LNCS 2470. Ithaca, NY, pages 93\u2013108. Berlin Heidelberg New York: Springer."},{"key":"9007_CR19","volume-title":"Computers and intractability: A guide to NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M. R. & Johnson, D. S. (1979). Computers and intractability: A guide to NP-completeness. San Francisco, California: Freeman."},{"key":"9007_CR20","unstructured":"Gottlob, G., Leone, N., & Scarcello, F. (1999). A comparison of structural CSP decomposition methods. In Proceedings IJCAI\u201999. Stockholm, Sweden, pages 394\u2013399."},{"key":"9007_CR21","unstructured":"Hnich, B., Kiziltan, Z., & Walsh, T. (2004). Combining symmetry breaking with other constraints: lexicographic ordering with sums. In Proceedings of the 8th International Symposium on the Artificial Intelligence and Mathematics. Fort Lauderdale, Florida, USA."},{"issue":"3","key":"9007_CR22","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"D.E. Knuth","year":"1992","unstructured":"Knuth, D. E., & Raghunathan, A. (1992). The problem of compatible representatives. SIAM J. Discrete Math. 5(3): 422\u2013427.","journal-title":"SIAM J. Discrete Math."},{"key":"9007_CR23","doi-asserted-by":"crossref","unstructured":"Lhomme, O. (2004). Arc-consistency filtering algorithms for logical combinations of constraints. In Proceedings CPAIOR\u201904. Nice, France, pages 209\u2013224.","DOI":"10.1007\/978-3-540-24664-0_15"},{"key":"9007_CR24","unstructured":"Mohr, R., & Masini, G. (1988). Good old discrete relaxation. In Proceedings ECAI\u201988, Munchen, Germany, pages 651\u2013656."},{"key":"9007_CR25","first-page":"331","volume-title":"Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming (CP\u201999), LNCS 1713. Alexandria, Virginia","author":"F. Pachet","year":"1999","unstructured":"Pachet, F., & Roy, P. (1999). Automatic generation of music programs. In Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming (CP\u201999), LNCS 1713. Alexandria, Virginia, pages 331\u2013345. Berlin Heidelberg New York: Springer."},{"key":"9007_CR26","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C.H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C. H., & Yannakakis, M. (1984). The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28: 244\u2013259.","journal-title":"J. Comput. Syst. Sci."},{"key":"9007_CR27","doi-asserted-by":"crossref","unstructured":"Quimper, C. (2003). Enforcing Domain Consistency on the Extended Global Cardinality Constraint is NP-hard. Technical Report CS-2003-39, School of Computer Science, University of Waterloo, Ontario, Canada.","DOI":"10.1007\/978-3-540-45193-8_41"},{"key":"9007_CR28","unstructured":"R\u00e9gin, J.C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings AAAI\u201994. Seattle, Washington, pages 362\u2013367. AAAI Press"},{"key":"9007_CR29","unstructured":"R\u00e9gin, J.C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings AAAI\u201996. Portland, Oregon, pages 209\u2013215. MIT."},{"key":"9007_CR30","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1023\/A:1020506526052","volume":"7","author":"J.C. R\u00e9gin","year":"2002","unstructured":"R\u00e9gin, J. C. (2002). Cost-based arc consistency for global cardinality constraints. Constraints 7: 387\u2013405.","journal-title":"Constraints"},{"key":"9007_CR31","first-page":"384","volume-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP\u201900), LNCS 1894. Singapore","author":"J.C. R\u00e9gin","year":"2000","unstructured":"R\u00e9gin, J. C., & Rueher, M. (2000). A global constraint combining a sum constraint and difference constraint. In Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP\u201900), LNCS 1894. Singapore, pages 384\u2013395. Berlin Heidelberg New York: Springer."},{"key":"9007_CR32","unstructured":"Sadler, A., & Gervet, C. (2001). Global reasoning on sets. In Proceedings of Workshop on Modelling and Problem Formulation (FORMUL\u201901), held alongside CP-01. Paphos, Cyprus."},{"key":"9007_CR33","first-page":"679","volume-title":"Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833. Kinsale, Ireland","author":"M. Sellmann","year":"2003","unstructured":"Sellmann, M. (2003). Approximated consistency for knapsack constraints. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833. Kinsale, Ireland, pages 679\u2013693. Berlin Heidelberg New York: Springer."},{"key":"9007_CR34","first-page":"694","volume-title":"Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833. Kinsale, Ireland","author":"M. Sellmann","year":"2003","unstructured":"Sellmann, M. (2003). Cost-based filtering for shorter path constraints. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833. Kinsale, Ireland, pages 694\u2013708. Berlin Heidelberg New York: Springer."},{"issue":"3","key":"9007_CR35","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1145\/210346.210347","volume":"42","author":"P. van Beek","year":"1995","unstructured":"van Beek, P., & Dechter, R. (1995). On the minimality and global consistency of row-convex constraint networks. J. ACM 42(3): 543\u2013561.","journal-title":"J. ACM"},{"key":"9007_CR36","unstructured":"Van Hentenryck, P., & Deville, Y. (1991). The cardinality operator: a new logical connective for constraint logic programming. In Proceedings ICLP\u201991. Paris, France, pages 745\u2013759."},{"issue":"1\u20133","key":"9007_CR37","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0743-1066(98)10006-7","volume":"37","author":"P. Van Hentenryck","year":"1998","unstructured":"Van Hentenryck, P., Saraswat, V., & Deville, Y. (1998). Design, implementation and evaluation of the constraint language cc(fd). J. Log. Program. 37(1\u20133): 139\u2013164.","journal-title":"J. Log. Program."},{"key":"9007_CR38","doi-asserted-by":"publisher","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 (September).","journal-title":"Constraints"},{"key":"9007_CR39","first-page":"724","volume-title":"Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833. Kinsale, Ireland","author":"T. Walsh","year":"2003","unstructured":"Walsh, T. (2003). Consistency and propagation with multiset constraints: a formal viewpoint. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833. Kinsale, Ireland, pages 724\u2013738. Berlin Heidelberg New York: Springer."},{"key":"9007_CR40","volume-title":"Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833, Kinsale, Ireland","author":"T. Walsh","year":"2003","unstructured":"Walsh, T. (2003). Constraint patterns. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP\u201903), LNCS 2833, Kinsale, Ireland. Berlin Heidelberg New York: Springer."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-006-9007-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-006-9007-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-006-9007-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-006-9007-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,17]],"date-time":"2022-05-17T18:01:49Z","timestamp":1652810509000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-006-9007-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12,2]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["9007"],"URL":"https:\/\/doi.org\/10.1007\/s10601-006-9007-3","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12,2]]},"assertion":[{"value":"21 March 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2006","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2006","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2006","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}