{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:17:44Z","timestamp":1740122264470,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,6,30]],"date-time":"2018-06-30T00:00:00Z","timestamp":1530316800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10601-018-9290-9","type":"journal-article","created":{"date-parts":[[2018,6,30]],"date-time":"2018-06-30T03:35:32Z","timestamp":1530329732000},"page":"355-382","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On a new extension of BTP for binary CSPs"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4880-8941","authenticated-orcid":false,"given":"Achref","family":"El Mouelhi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,30]]},"reference":[{"key":"9290_CR1","first-page":"95","volume":"7","author":"U Montanari","year":"1974","unstructured":"Montanari, U. (1974). Networks of constraints: fundamental properties and applications to picture processing. Artificial Intelligence, 7, 95\u2013132.","journal-title":"Artificial Intelligence"},{"key":"9290_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"AK Mackworth","year":"1977","unstructured":"Mackworth, A.K. (1977). Consistency in networks of relations. Artificial Intelligence, 8, 99\u2013118.","journal-title":"Artificial Intelligence"},{"key":"9290_CR3","unstructured":"Freuder, E.C. (1991). Eliminating interchangeable values in constraint satisfaction problems. In Proceedings of the 9th national conference on artificial intelligence, (Vol. 1 pp. 227\u2013233)."},{"key":"9290_CR4","doi-asserted-by":"crossref","unstructured":"Likitvivatanavong, C., & Yap, R.H.C. (2013). Many-to-many interchangeable sets of values in csps. In Proceedings of SAC (pp. 86\u201391).","DOI":"10.1145\/2480362.2480382"},{"key":"9290_CR5","doi-asserted-by":"crossref","unstructured":"Cooper, M.C., El Mouelhi, A., Terrioux, C., Zanuttini, B. (2014). On Broken Triangles. In Principles and practice of constraint programming - 20th international conference, CP 2014. Proceedings (pp. 9\u201324).","DOI":"10.1007\/978-3-319-10428-7_5"},{"key":"9290_CR6","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.artint.2016.02.001","volume":"234","author":"MC Cooper","year":"2016","unstructured":"Cooper, M.C., Duchein, A., El Mouelhi, A., 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"},{"key":"9290_CR7","unstructured":"Cohen, D.A., Cooper, M.C., Escamocher, G., Zivny, S. (2013). Variable elimination in binary CSP via forbidden patterns. In IJCAI 2013, Proceedings of the 23rd international joint conference on artificial intelligence (pp. 517\u2013523)."},{"issue":"7","key":"9290_CR8","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1016\/j.jcss.2015.02.001","volume":"81","author":"DA Cohen","year":"2015","unstructured":"Cohen, D.A., Cooper, M.C., Escamocher, G., Zivny, S. (2015). Variable and value elimination in binary constraint satisfaction via forbidden patterns. Journal of Computer and System Sciences, 81(7), 1127\u20131143.","journal-title":"Journal of Computer and System Sciences"},{"key":"9290_CR9","unstructured":"Dechter, A., & Dechter, R. (1987). Removing redundancies in constraint networks. In Proceedings of the 6th national conference on artificial intelligence (pp. 105\u2013109)."},{"key":"9290_CR10","unstructured":"Cooper, M.C., Jeavons, P., Salamon, A. (2008). Hybrid tractable CSPs which generalize tree structure. In Proceedings of ECAI (pp. 530\u2013534)."},{"key":"9290_CR11","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1016\/j.artint.2010.03.002","volume":"174","author":"MC Cooper","year":"2010","unstructured":"Cooper, M.C., Jeavons, P., Salamon, A. (2010). Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination. Artificial Intelligence, 174, 570\u2013584.","journal-title":"Artificial Intelligence"},{"issue":"4","key":"9290_CR12","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1080\/0952813X.2012.721138","volume":"25","author":"W Naanaa","year":"2013","unstructured":"Naanaa, W. (2013). Unifying and extending hybrid tractable classes of csps. Journal of Experimental & Theoretical Artificial Intelligence, 25(4), 407\u2013424.","journal-title":"Journal of Experimental & Theoretical Artificial Intelligence"},{"key":"9290_CR13","doi-asserted-by":"crossref","unstructured":"Cooper, M.C. (2014). Beyond consistency and substitutability. In Principles and practice of constraint programming - 20th international conference, CP 2014. Proceedings (pp. 256\u2013271).","DOI":"10.1007\/978-3-319-10428-7_20"},{"key":"9290_CR14","doi-asserted-by":"crossref","unstructured":"El Mouelhi, A., J\u00e9gou, P., Terrioux, C. (2014). Hidden tractable classes: from theory to practice. In 26th IEEE international conference on tools with artificial intelligence, ICTAI, 2014 (pp. 437\u2013445).","DOI":"10.1109\/ICTAI.2014.73"},{"issue":"4","key":"9290_CR15","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10601-015-9185-y","volume":"20","author":"A El Mouelhi","year":"2015","unstructured":"El Mouelhi, A., J\u00e9gou, P., Terrioux, C. (2015). A hybrid tractable class for non-binary CSPs. Constraints, 20(4), 383\u2013413.","journal-title":"Constraints"},{"key":"9290_CR16","doi-asserted-by":"crossref","unstructured":"J\u00e9gou, P., & Terrioux, C. (2015). The extendable-triple property: A new CSP tractable class beyond BTP. In Proceedings of AAAI (pp. 3746\u20133754).","DOI":"10.1609\/aaai.v29i1.9754"},{"key":"9290_CR17","doi-asserted-by":"crossref","unstructured":"Cooper, M.C., J\u00e9gou, P., Terrioux, C. (2015). A microstructure-based family of tractable classes for CSPs. In Principles and practice of constraint programming - 21st international conference, CP, 2015, Proceedings (pp. 74\u201388).","DOI":"10.1007\/978-3-319-23219-5_6"},{"key":"9290_CR18","unstructured":"Naanaa, W. (2016). Extending the broken triangle property tractable class of binary csps. In Proceedings of the 9th hellenic conference on artificial intelligence, SETN, 2016 (pp. 3:1\u20133:6)."},{"key":"9290_CR19","doi-asserted-by":"crossref","unstructured":"Cooper, M.C., El Mouelhi, A., Terrioux, C. (2016). Extending broken triangles and enhanced value-merging. In Principles and practice of constraint programming - 22nd international conference, CP 2016, Proceedings (pp. 173\u2013188).","DOI":"10.1007\/978-3-319-44953-1_12"},{"key":"9290_CR20","doi-asserted-by":"crossref","unstructured":"Sabin, D., & Freuder, E.C. (1994). Contradicting Conventional Wisdom in Constraint Satisfaction. In Proceedings of ECAI (pp. 125\u2013129).","DOI":"10.1007\/3-540-58601-6_86"},{"key":"9290_CR21","unstructured":"Nadel, B. (1988). Tree search and arc consistency in constraint-satisfaction algorithms. In Search in artificial intelligence (pp. 287\u2013342). Berlin: Springer."},{"key":"9290_CR22","doi-asserted-by":"crossref","unstructured":"El Mouelhi, A. (2017). A btp-based family of variable elimination rules for binary csps. In To appear inproceedings of the thirty-first AAAI conference on artificial intelligence.","DOI":"10.1609\/aaai.v31i1.11126"},{"key":"9290_CR23","unstructured":"Dechter, R., & Pearl, J. (1987). The Cycle-cutset method for improving search performance in AI Applications. In Proceedings of the third IEEE on artificial intelligence applications (pp. 224\u2013230)."},{"key":"9290_CR24","unstructured":"Rossi, F., Petrie, C.J., Dhar, V. (1990). On the equivalence of constraint satisfaction problems. In ECAI (pp. 550\u2013556)."},{"key":"9290_CR25","unstructured":"J\u00e9gou, P. (1993). Decomposition of domains based on the micro-structure of finite constraint satisfaction problems. In Proceedings of the 11th national conference on artificial intelligence, 1993 (pp. 731\u2013736)."},{"key":"9290_CR26","doi-asserted-by":"crossref","unstructured":"El Mouelhi, A., J\u00e9gou, P., Terrioux, C., Zanuttini, B. (2013). Some new tractable classes of csps and their relations with backtracking algorithms. In 10th international conference integration of AI and OR techniques in constraint programming for combinatorial optimization problems, CPAIOR 2013, May 18-22, 2013. Proceedings (pp. 61\u201376).","DOI":"10.1007\/978-3-642-38171-3_5"},{"issue":"2","key":"9290_CR27","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"P Jeavons","year":"1995","unstructured":"Jeavons, P., & Cooper, M. (1995). Tractable constraints on ordered domains. Artificial Intelligence, 79(2), 327\u2013339.","journal-title":"Artificial Intelligence"},{"key":"9290_CR28","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. Artificial Intelligence, 38, 353\u2013366.","journal-title":"Artificial Intelligence"},{"key":"9290_CR29","doi-asserted-by":"crossref","unstructured":"El Mouelhi, A., J\u00e9gou, P., Terrioux, C. (2013). A hybrid tractable class for non-binary CSPs. In 2013 IEEE 25th international conference on tools with artificial intelligence, November 4-6, 2013 (pp. 947\u2013954).","DOI":"10.1109\/ICTAI.2013.144"},{"key":"9290_CR30","unstructured":"El Mouelhi, A., J\u00e9gou, P., Terrioux, C. (2013). Microstructures for csps with constraints of arbitrary arity. In Proceedings of the Tenth symposium on abstraction, reformulation, and approximation, SARA 2013, 11-12 July 2013."},{"issue":"1","key":"9290_CR31","doi-asserted-by":"publisher","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. JACM, 29(1), 24\u201332.","journal-title":"JACM"},{"key":"9290_CR32","unstructured":"El Mouelhi, A. (2014). Classes polynomiales pour CSP : De la th\u00e9orie \u00e0 la pratique. Ph.D. thesis, Aix-Marseille Universit\u00e9."},{"key":"9290_CR33","unstructured":"J\u00e9gou, P. (1993). On the consistency of general constraint-satisfaction problems. In Proceedings of the 11th national conference on artificial intelligence. July 11-15, 1993 (pp. 114\u2013119)."},{"key":"9290_CR34","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1613\/jair.834","volume":"14","author":"R Debruyne","year":"2001","unstructured":"Debruyne, R., & Bessi\u00e8re, C. (2001). Domain filtering consistencies. Journal of Artificial Intelligence Research, 14, 205\u2013230.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9290_CR35","doi-asserted-by":"crossref","unstructured":"Cooper, M.C., & Zivny, S. (2016). The power of arc consistency for CSPs defined by partially-ordered forbidden patterns. In Proceedings of the 31st annual ACM\/IEEE symposium on logic in computer science, LICS \u201916, 2016 (pp. 652\u2013661).","DOI":"10.1145\/2933575.2933587"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-018-9290-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9290-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9290-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,26]],"date-time":"2022-08-26T20:02:16Z","timestamp":1661544136000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-018-9290-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,30]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["9290"],"URL":"https:\/\/doi.org\/10.1007\/s10601-018-9290-9","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2018,6,30]]},"assertion":[{"value":"30 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}