{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T15:40:02Z","timestamp":1748446802280,"version":"3.41.0"},"reference-count":39,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1051\/ro\/2015017","type":"journal-article","created":{"date-parts":[[2015,6,12]],"date-time":"2015-06-12T06:45:30Z","timestamp":1434091530000},"page":"241-267","source":"Crossref","is-referenced-by-count":1,"title":["Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints"],"prefix":"10.1051","volume":"50","author":[{"given":"Zineb","family":"Habbas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kamal","family":"Amroun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Singer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2016,3,21]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"I. Adler, G. Gottlob and M. Grohe, Hypertree-width and related hypergraph invariants. InProc. of the 3rd European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB\u201905), DMTCS Proceedings Series, vol. AE (2005) 5\u201310.","DOI":"10.46298\/dmtcs.3424"},{"key":"R2","unstructured":"A. Ait-Amokhtar, K. Amroun and Z. Habbas, Hypertree Decomposition for Solving Constraint Satisfaction Problems. InProc. of International conference on Agents and Artificial Intelligence, ICAART\u20192009(2009) 398\u2013404."},{"key":"R3","unstructured":"C. Bessi\u00e8re and J.C. R\u00e9gin, Arc Consistency for General Constraint Networks: Preliminary Results. InProc. of the Sixtenteenth International Joint Conference on Artificial Intelligence(1997) 398\u2013404."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Cohen D., Jeavons P. and Gyssens M., A unified theory of structural tractability for Constraint Satisfaction Problems.J. Comput. System Sci.74(2008) 721\u2013743.","DOI":"10.1016\/j.jcss.2007.08.001"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Dechter R. and Pearl J., Tree clustering for constraint networks.J. Artif. Intell.38(1989) 353\u2013366.","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"R6","unstructured":"A. Dermaku, T. Ganzow, G. Gottlob, B. McMahan, N. Musliu and M. Samer, Heuristic Methods for Hypertree Decompositions. InProc. of the 7th. Mexican Int. Conf. on Artificial Intelligence: Advances in Artificial Intelligence(2008) 1\u201311."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Freuder E.C., A sufficient condition for Backtrack-free search.J. ACM29(1982) 24\u201332.","DOI":"10.1145\/322290.322292"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Freuder E.C., A sufficient condition for backtrack-bounded search.J. ACM32(1985) 755\u2013761.","DOI":"10.1145\/4221.4225"},{"key":"R9","unstructured":"I.P. Gent, C. Jefferson and P. Nightingale, Data Structures for Generalized arc Consistency for Extensional Constraints. InProc. of AAAI\u201907(2007) 191\u2013197."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Gottlob G. and Samer M., A Backtracking-based algorithm for hypertree decomposition.ACM J. Exp. Algorithmics (JEA)13(2009).","DOI":"10.1145\/1412228.1412229"},{"key":"R11","unstructured":"Gottlob G., Leone N. and Scarcello F., A comparison of structural CSP decomposition methods.Artif. Intell.124(2000) 243\u2013282."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Gottlob G., Leone N. and Scarcello F., Hypertree decompositions and tractable queries.J. Comput. System Sci.64(2002) 579\u2013627.","DOI":"10.1006\/jcss.2001.1809"},{"key":"R13","unstructured":"Gottlob G., Leone N. and Scarcello F., Robbers, marshals, and guards: game theoretic and logical characterisations of hypertree width.J. Comput. System Sci.66(2003) 775\u2013808."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Gottlob G., Miklos Z. and Schwentick T., Generalized hypertree decompositions: NP \u2013 hardness and tractable variants.J. ACM56(2009).","DOI":"10.1145\/1568318.1568320"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Grohe and D. Marx, Constraint Solving via Fractional Edge Covers. InProc. of SODA 2006(2006) 289\u2013298.","DOI":"10.1145\/1109557.1109590"},{"key":"R16","unstructured":"Gyssens M., Jeavons P.G. and Cohen D.A., Decomposing constraint satisfaction problems using database techniques.Artif. Intell. J.66(1994) 57\u201389."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"P. Harvey and A. Ghose, Reducing Redundancy in The Hypertree Decomposition Scheme. InProc. of ICTAI\u201903, Montreal (2003) 474\u2013481.","DOI":"10.1109\/TAI.2003.1250227"},{"key":"R18","unstructured":"Hyafil L. and Rivest R.L., Constructing optimal binary decision trees is NP-complete.Inf. Process. Lett.5(1976) 15\u201317."},{"key":"R19","unstructured":"J\u00e9gou P. and Terrioux C., Hybrid backtracking bounded by tree-decomposition of constraint networks.Artif. Intell. J.146(2003) 43\u201375."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"P. J\u00e9gou, S.N. Ndiaye and C. Terrioux, Combined Strategies for Decomposition-based Methods for Solving CSPs. InProc. of ICTAI\u201909(2009) 184\u2013192.","DOI":"10.1109\/ICTAI.2009.70"},{"key":"R21","unstructured":"Kam T., Villa T., Brayton R.K. and Sangiovanni-Vincentelli A.L., Multivalued decision diagrams: Theory and applications.Int. J. Multiple Valued Logic4(1998) 9\u201362."},{"key":"R22","unstructured":"G. Katsirelos and F. Bacchus, Generalized Nogoods in CSPs. InProc. of AAAI\u201905, Pittsburgh (2005) 390\u2013396."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"G. Katsirelos and T. Walsh, A Compression Algorithm for Large Arity Extensional Constraints. InProc. of CP\u201907(2007) 379\u2013393.","DOI":"10.1007\/978-3-540-74970-7_28"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Kenil Cheng C.K. and Yap R.H.C., An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints.Constraints15(2010) 265\u2013304.","DOI":"10.1007\/s10601-009-9087-y"},{"key":"R25","unstructured":"T. Korimort,Heuristic hypertree decomposition. Ph. D. thesis, Vienna University of Technology (2003)."},{"key":"R26","unstructured":"Lecoutre C., STR2: optimized simple table reduction for table constraints.Constraints16(2011) 341\u2013371."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"A. Mackworth, On Reading Sketch Maps. InProc. of IJCAI-77(1977) 598\u2013606.","DOI":"10.1021\/cr60308a901"},{"key":"R28","unstructured":"Z. Miklos,Understanding Tractable Decompositions for Constraint Satisfaction. Ph. D. thesis, University of Oxford (2008)."},{"key":"R29","unstructured":"Montanari U., Networks of constraints: fundamental properties and applications to pictures processing.Inf. Sci. J.7(1974) 95\u2013132."},{"key":"R30","unstructured":"Musliu N. and Schafhauser W., Genetic algorithms for Generalized hypertree decompositions.Eur. J. Ind. Eng.1(2005) 317\u2013340."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"W. Pang and S.D. Goodwin, Constraint-directed backtracking. Vol. 1342 ofLect. Notes Comput. Sci.(1997) 47\u201356.","DOI":"10.1007\/3-540-63797-4_57"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"W. Pang and S.D. Goodwin, A graph based backtracking algorithm for solving general CSPs.Lect. Notes Comput. Sci. of AI(2003) 114\u2013128.","DOI":"10.1007\/3-540-44886-1_11"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"G. Pesant, A Regular Language Membership Constraint for Finite Sequences of Variables. InProc. of CP\u201904(2004) 482\u2013495.","DOI":"10.1007\/978-3-540-30201-8_36"},{"key":"R34","unstructured":"J.-C. R\u00e9gin, Improving the Expressiveness of Table Constraints. InProc. of workshop ModRef 11 at CP\u201911(2011)."},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Robertson N. and Seymour P.D., Graph minors .II. algorithmic aspects of treewidth.J. Algorithms7(1986) 309\u2013322.","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"R36","unstructured":"M. Samer, Hypertree-DecompositionviaBranch-Decomposition. InProc. of IJCAI\u201905(2005) 1535\u20131536."},{"key":"R37","unstructured":"S. Subbarayan and H. Reif Anderson, Backtracking Procedures for Hypertree, Hyperspread and Connected Hypertree Decomposition of CSPs. InProc. of IJCAI\u201907(2007) 180\u2013185."},{"key":"R38","unstructured":"Ullmann J.R., Partition search for non binary constraint satisfaction.Inf. Sci. J.177(2007) 3639\u20133678."},{"key":"R39","unstructured":"M. Yannakakis, Algorithms for Acyclic Database Schemes. InProc. of VLDB\u201981. Edited by C. Zaniolo and C. Delobel, Cannes, France (1981) 82\u201394."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2015017\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T15:27:37Z","timestamp":1748446057000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2015017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,21]]},"references-count":39,"journal-issue":{"issue":"2"},"alternative-id":["ro150017"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2015017","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2016,3,21]]}}}