{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:17:07Z","timestamp":1740122227776,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,8,2]],"date-time":"2016-08-02T00:00:00Z","timestamp":1470096000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche (FR)","doi-asserted-by":"publisher","award":["ANR-2010-BLAN-0210"],"award-info":[{"award-number":["ANR-2010-BLAN-0210"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s10601-016-9248-8","type":"journal-article","created":{"date-parts":[[2016,8,2]],"date-time":"2016-08-02T04:23:07Z","timestamp":1470111787000},"page":"191-229","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Combining restarts, nogoods and bag-connected decompositions for solving CSPs"],"prefix":"10.1007","volume":"22","author":[{"given":"Philippe","family":"J\u00e9gou","sequence":"first","affiliation":[]},{"given":"Cyril","family":"Terrioux","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,2]]},"reference":[{"key":"9248_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D., & Proskuroswki, A. (1987). Complexity of finding embeddings in a k-tree. SIAM Journal of Discrete Mathematics, 8, 277\u2013284.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"9248_CR2","unstructured":"Berge, C. (1973). Graphs and Hypergraphs. Elsevier."},{"key":"9248_CR3","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0004-3702(02)00263-1","volume":"141","author":"C Bessi\u00e8re","year":"2002","unstructured":"Bessi\u00e8re, C., Meseguer, P., Freuder, E.C., & Larrosa, J. (2002). On forward checking for non-binary constraint satisfaction. Artificial Intelligence, 141, 205\u2013224.","journal-title":"Artificial Intelligence"},{"key":"9248_CR4","unstructured":"Bessi\u00e8re, C., & R\u00e9gin, J.C. (2001). Refining the basic constraint propagation algorithm. In Proceedings of IJCAI (pp. 309\u2013315)."},{"key":"9248_CR5","unstructured":"Boussemart, F., Hemery, F., Lecoutre, C., & Sais, L. (2004). Boosting systematic search by weighting constraints. In Proceedings of ECAI (pp. 146\u2013150)."},{"key":"9248_CR6","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1023\/A:1009812409930","volume":"4","author":"C Cabon","year":"1999","unstructured":"Cabon, C, de Givry, S., Lobjois, L., Schiex, T., & Warners, J.P. (1999). Radio link frequency assignment. Constraints, 4, 79\u201389.","journal-title":"Constraints"},{"key":"9248_CR7","unstructured":"Dechter, R. (2003). Constraint processing. Morgan Kaufmann Publishers."},{"key":"9248_CR8","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0004-3702(00)00050-3","volume":"125","author":"R Dechter","year":"2001","unstructured":"Dechter, R., & Fattah, Y.E. (2001). Topological parameters for time-space tradeoff. Artificial Intelligence, 125, 93\u2013118.","journal-title":"Artificial Intelligence"},{"key":"9248_CR9","doi-asserted-by":"crossref","unstructured":"Dechter, R., & Mateescu, R. (2004). The impact of AND\/OR search spaces on constraint satisfaction and counting. In Proceedings of the 10th international conference on principles and practice of constraint programming (CP) (pp. 731\u2013736).","DOI":"10.1007\/978-3-540-30201-8_56"},{"key":"9248_CR10","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.artint.2006.11.003","volume":"171","author":"R Dechter","year":"2007","unstructured":"Dechter, R., & Mateescu, R. (2007). AND\/OR search spaces for graphical models. Artificial Intelligence, 171, 73\u2013106.","journal-title":"Artificial Intelligence"},{"key":"9248_CR11","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":"9248_CR12","doi-asserted-by":"crossref","unstructured":"Dermaku, A., Ganzow, T., Gottlob, G., McMahan, B.J., Musliu, N., & Samer, M. (2008). Heuristic methods for hypertree decomposition. In Proceedings of MICAI (pp. 1\u201311).","DOI":"10.1007\/978-3-540-88636-5_1"},{"key":"9248_CR13","unstructured":"Diestel, R., & M\u00fcller, M. (2014). Connected tree-width. arXiv: 1211.7353v2 ."},{"key":"9248_CR14","doi-asserted-by":"crossref","unstructured":"Favier, A, de Givry, S., & J\u00e9gou, P. (2009). Exploiting problem structure for solution counting. In Proceedings of CP (pp. 335\u2013343).","DOI":"10.1007\/978-3-642-04244-7_27"},{"key":"9248_CR15","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., & Nisse, N. (2006). Connected treewidth and connected graph searching. In Proceedings of LATIN (pp. 479\u2013490).","DOI":"10.1007\/11682462_45"},{"issue":"1","key":"9248_CR16","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E Freuder","year":"1982","unstructured":"Freuder, E. (1982). A sufficient condition for backtrack-free search. Journal of the ACM, 29(1), 24\u201332.","journal-title":"Journal of the ACM"},{"issue":"2","key":"9248_CR17","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril, F. (1972). Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2), 180\u2013187.","journal-title":"SIAM Journal on Computing"},{"key":"9248_CR18","volume-title":"Algorithmic graph theory and perfect graphs","author":"M Golumbic","year":"1980","unstructured":"Golumbic, M. (1980). Algorithmic graph theory and perfect graphs. New York: Academic Press."},{"issue":"1\/2","key":"9248_CR19","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1023\/A:1006314320276","volume":"24","author":"CP Gomes","year":"2000","unstructured":"Gomes, C.P., Selman, B., Crato, N., & Kautz, H.A. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning, 24(1\/2), 67\u2013100.","journal-title":"Journal of Automated Reasoning"},{"key":"9248_CR20","doi-asserted-by":"crossref","first-page":"243","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, 243\u2013282.","journal-title":"Artificial Intelligence"},{"key":"9248_CR21","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., & Cohen, D. (1994). Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence, 66, 57\u201389.","journal-title":"Artificial Intelligence"},{"key":"9248_CR22","unstructured":"Hamann, M., & Wei\u00dfauer, D. (2015). Bounding connected tree-width. ArXiv: 1503.01592 ."},{"key":"9248_CR23","unstructured":"Harvey, W.D. (1995). Nonsystematic backtracking search. Ph.D. thesis, Stanford University."},{"key":"9248_CR24","doi-asserted-by":"crossref","unstructured":"J\u00e9gou, P., Ndiaye, S.N., & Terrioux, C. (2005). Computing and exploiting tree-decompositions for solving constraint networks. In Proceedings of CP (pp. 777\u2013781).","DOI":"10.1007\/11564751_63"},{"key":"9248_CR25","doi-asserted-by":"crossref","unstructured":"J\u00e9gou, P., Ndiaye, S.N., & Terrioux, C. (2006). An extension of complexity bounds and dynamic heuristics for tree-decompositions of CSP. In Proceedings of CP (pp. 741\u2013745).","DOI":"10.1007\/11889205_62"},{"key":"9248_CR26","unstructured":"J\u00e9gou, P., Ndiaye, S.N., & Terrioux, C. (2007). Dynamic heuristics for backtrack search on tree-decomposition of CSPs. In Proceedings of IJCAI (pp. 112\u2013117)."},{"key":"9248_CR27","doi-asserted-by":"crossref","unstructured":"J\u00e9gou, P., Ndiaye, S.N., & Terrioux, C. (2007). Dynamic management of heuristics for solving structured CSPs. In Proceedings of CP (pp. 364\u2013378).","DOI":"10.1007\/978-3-540-74970-7_27"},{"key":"9248_CR28","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0004-3702(02)00400-9","volume":"146","author":"P J\u00e9gou","year":"2003","unstructured":"J\u00e9gou, P., & Terrioux, C. (2003). Hybrid backtracking bounded by tree-decomposition of constraint networks. Artificial Intelligence, 146, 43\u201375.","journal-title":"Artificial Intelligence"},{"key":"9248_CR29","unstructured":"J\u0117gou, P., & Terrioux, C. (2014). Combining restarts, nogoods and decompositions for solving csps. In Proceedings of ECAI (pp. 465\u2013470)."},{"key":"9248_CR30","doi-asserted-by":"crossref","unstructured":"J\u0117gou, P., & Terrioux, C. (2014). Tree-decompositions with connected clusters for solving constraint networks. In Proceedings of CP (pp. 407\u2013423).","DOI":"10.1007\/978-3-319-10428-7_31"},{"key":"9248_CR31","doi-asserted-by":"crossref","unstructured":"Karakashian, S., Woodward, R., & Choueiry, B.Y. (2013). Improving the performance of consistency algorithms by localizing and bolstering propagation in a tree decomposition. In Proceedings of AAAI (pp. 466\u2013473).","DOI":"10.1609\/aaai.v27i1.8594"},{"key":"9248_CR32","unstructured":"Kjaerulff, U. (1990). Triangulation of graphs - algorithms giving small total state space. Tech. rep., Judex R.R. Aalborg, Denmark."},{"key":"9248_CR33","unstructured":"Lecoutre, C. (2009). Constraint networks - techniques and algorithms. ISTE\/Wiley."},{"issue":"3\u20134","key":"9248_CR34","first-page":"147","volume":"1","author":"C Lecoutre","year":"2007","unstructured":"Lecoutre, C., Sa\u00efs, L., Tabary, S., & Vidal, V. (2007). Recording and minimizing nogoods from restarts. JSAT, 1(3\u20134), 147\u2013167.","journal-title":"JSAT"},{"issue":"4","key":"9248_CR35","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0020-0190(93)90029-9","volume":"47","author":"M Luby","year":"1993","unstructured":"Luby, M., Sinclair, A., & Zuckerman, D. (1993). Optimal speedup of Las Vegas algorithms. Information Processing Letters, 47(4), 173\u2013180.","journal-title":"Information Processing Letters"},{"key":"9248_CR36","unstructured":"M\u00fcller, M. (2012). Connected tree-width. ArXiv: 1211.7353 ."},{"key":"9248_CR37","doi-asserted-by":"crossref","unstructured":"Nadel, B. (1988). Tree search and arc consistency in constraint-satisfaction algorithms. In Search in artificial intelligence (pp. 287\u2013342). Springer-Verlag.","DOI":"10.1007\/978-1-4613-8788-6_9"},{"key":"9248_CR38","unstructured":"Petke, J. (2012). On the bridge between constraint satisfaction and Boolean satisfiability. Ph.D. thesis, University of Oxford."},{"key":"9248_CR39","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., & Seymour, P. (1986). Graph minors II: algorithmic aspects of treewidth. Algorithms, 7, 309\u2013322.","journal-title":"Algorithms"},{"key":"9248_CR40","unstructured":"Rose, D.J. (1973). A graph theoretic study of the numerical solution of sparse positive denite systems of linear equations. In Read, R.C. (Ed.) Graph theory and computing (pp. 183\u2013217). New York: Academic Press."},{"key":"9248_CR41","unstructured":"Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of constraint programming. Elsevier."},{"key":"9248_CR42","doi-asserted-by":"crossref","unstructured":"Sabin, D., & Freuder, E. (1994). Contradicting conventional wisdom in constraint satisfaction. In Proceedings of ECAI (pp. 125\u2013129).","DOI":"10.1007\/3-540-58601-6_86"},{"key":"9248_CR43","doi-asserted-by":"crossref","unstructured":"Sabin, D., & Freuder, E. (1997). Understanding and improving the MAC algorithm. In Proceedings of CP (pp. 167\u2013181).","DOI":"10.1007\/BFb0017438"},{"key":"9248_CR44","unstructured":"Sanchez, M., Bouveret, S, de Givry, S., Heras, F., J\u00e9gou, P., Larrosa, J., Ndiaye, S.N., Rollon, E., Schiex, T., Terrioux, C., Verfaillie, G., & Zytnicki, M. (2008). Max-CSP competition 2008: toulbar2 solver description. In Proceedings of the 3rd CSP solver competition, CP workshop (pp. 63\u201370)."},{"issue":"3","key":"9248_CR45","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R Tarjan","year":"1984","unstructured":"Tarjan, R., & Yannakakis, M. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3), 566\u2013579.","journal-title":"SIAM Journal on Computing"},{"key":"9248_CR46","unstructured":"Walsh, T. (1999). Search in a small world. In Proceedings of IJCAI (pp. 1172\u20131177)."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-016-9248-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9248-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9248-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9248-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T17:49:26Z","timestamp":1656956966000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-016-9248-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,2]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["9248"],"URL":"https:\/\/doi.org\/10.1007\/s10601-016-9248-8","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2016,8,2]]}}}