{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T09:32:31Z","timestamp":1780651951833,"version":"3.54.1"},"reference-count":46,"publisher":"Elsevier","isbn-type":[{"value":"9780444527264","type":"print"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1016\/s1574-6526(06)80011-8","type":"book-chapter","created":{"date-parts":[[2008,2,26]],"date-time":"2008-02-26T16:51:39Z","timestamp":1204044699000},"page":"209-244","source":"Crossref","is-referenced-by-count":24,"title":["Tractable Structures for Constraint Satisfaction Problems"],"prefix":"10.1016","member":"78","reference":[{"key":"10.1016\/S1574-6526(06)80011-8_bib1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","article-title":"Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2014 a survey","volume":"25","author":"Arnborg","year":"1985","journal-title":"BIT"},{"key":"10.1016\/S1574-6526(06)80011-8_bib2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"10.1016\/S1574-6526(06)80011-8_bib3","series-title":"AAAI'96: Proceedings of the Thirteenth National Conference on Artificial Intelligence","first-page":"298","article-title":"A complexity analysis of space-bound learning algorithms for the constraint satisfaction problem","author":"Bayardo","year":"1996"},{"key":"10.1016\/S1574-6526(06)80011-8_bib4","series-title":"Uncertainty in AI (UAI'96)","first-page":"81","article-title":"A sufficiently fast algorithm for finding close to optimal junction trees","author":"Becker","year":"1996"},{"key":"10.1016\/S1574-6526(06)80011-8_bib5","series-title":"Uncertainty in AI (UAI'99)","first-page":"81","article-title":"Random algorithms for the loop-cutset problem","author":"Becker","year":"1999"},{"issue":"3","key":"10.1016\/S1574-6526(06)80011-8_bib6","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1145\/2402.322389","article-title":"On the desirability of acyclic database schemes","volume":"30","author":"Beeri","year":"1983","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80011-8_bib7","series-title":"Nonserial Dynamic Programming","author":"Bertele","year":"1972"},{"key":"10.1016\/S1574-6526(06)80011-8_bib8","series-title":"Uncertainty in AI (UAI04)","article-title":"On finding w-cutset in Bayesian networks","author":"Bidyuk","year":"2004"},{"key":"10.1016\/S1574-6526(06)80011-8_bib9","series-title":"MFCS-97","first-page":"19","article-title":"Treewidth: Algorithmic techniques and results","author":"Bodlaender","year":"1997"},{"key":"10.1016\/S1574-6526(06)80011-8_bib10","series-title":"Technical report RUUCS-91-1, Utrecht University","article-title":"Approximating treewidth, pathwidth and minimum elimination tree-height","author":"Bodlaender","year":"1991"},{"key":"10.1016\/S1574-6526(06)80011-8_bib11","series-title":"UCI Technical report","article-title":"And\/or search spaces for graphical models","author":"Dechter","year":"2005"},{"key":"10.1016\/S1574-6526(06)80011-8_bib12","series-title":"Constraint Processing","author":"Dechter","year":"2003"},{"key":"10.1016\/S1574-6526(06)80011-8_bib13","first-page":"276","article-title":"Constraint networks","author":"Dechter","year":"1992","journal-title":"Encyclopedia of Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib14","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","article-title":"Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition","volume":"41","author":"Dechter","year":"1990","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib15","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","article-title":"Bucket elimination: A unifying framework for reasoning","volume":"113","author":"Dechter","year":"1999","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib16","series-title":"Proceeding of Constraint Programming (CP2004)","first-page":"731","article-title":"The impact of and\/or search spaces on constraint satisfaction and counting","author":"Dechter","year":"2004"},{"key":"10.1016\/S1574-6526(06)80011-8_bib17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","article-title":"Network-based heuristics for constraint satisfaction problems","volume":"34","author":"Dechter","year":"1987","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib18","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","article-title":"Tree clustering for constraint networks","author":"Dechter","year":"1989","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib19","series-title":"Computer Science Press","article-title":"Graph algorithms","author":"Even","year":"1979"},{"key":"10.1016\/S1574-6526(06)80011-8_bib20","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/18.suppl_1.S189","article-title":"Exact genetic linkage computations for general pedigrees","author":"Fishelson","year":"2002","journal-title":"Bioinformatics"},{"key":"10.1016\/S1574-6526(06)80011-8_bib21","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/640075.640089","article-title":"Optimizing exact genetic linkage computations","author":"Fishelson","year":"2003","journal-title":"RECOMB"},{"key":"10.1016\/S1574-6526(06)80011-8_bib22","doi-asserted-by":"crossref","DOI":"10.1159\/000084736","article-title":"Maximum likelihood haplotyping for general pedigrees","author":"Fishelson","year":"2005","journal-title":"Human Heredity"},{"issue":"1","key":"10.1016\/S1574-6526(06)80011-8_bib23","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","article-title":"A sufficient condition for backtrack-free search","volume":"29","author":"Freuder","year":"1982","journal-title":"Journal of the ACM"},{"issue":"1","key":"10.1016\/S1574-6526(06)80011-8_bib24","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1145\/4221.4225","article-title":"A sufficient condition for backtrack-bounded search","volume":"32","author":"Freuder","year":"1985","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80011-8_bib25","series-title":"Joint International Conference of Artificial Intelligence","article-title":"Taking advantage of stable sets of variables in constraint satisfaction problems","author":"Freuder","year":"1985"},{"key":"10.1016\/S1574-6526(06)80011-8_bib26","article-title":"The use of lineal spanning trees to represent constraint satisfaction problems","author":"Freuder","year":"1987"},{"issue":"1\u20133","key":"10.1016\/S1574-6526(06)80011-8_bib27","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0004-3702(92)90004-H","article-title":"Partial constraint satisfaction","volume":"58","author":"Freuder","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib28","article-title":"Performance measurement and analysis of search algorithms","author":"Gaschnig","year":"1979"},{"key":"10.1016\/S1574-6526(06)80011-8_bib29","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","article-title":"A comparison of structural CSP decomposition methods","author":"Gottlob","year":"2000","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib30","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1145\/382780.382783","article-title":"The complexity of acyclic conjunctive queries","author":"Gottlob","year":"2001","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80011-8_bib31","article-title":"Non-binary constraints and optimal dual-graph representations","author":"Greco","year":"2003","journal-title":"Ijcai-03"},{"key":"10.1016\/S1574-6526(06)80011-8_bib32","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","article-title":"Decomposing constraint satisfaction problems using database techniques","volume":"66","author":"Gyssens","year":"1994","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"10.1016\/S1574-6526(06)80011-8_bib33","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.artint.2005.04.004","article-title":"Unifying tree-decompositions for reasoning in graphical models","volume":"166","author":"Kask","year":"2005","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib34","article-title":"Dynamic combination of search and variable-elimination in CSP and Max-CSP","author":"Larrosa","year":"2001","journal-title":"Submitted"},{"issue":"2","key":"10.1016\/S1574-6526(06)80011-8_bib35","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","article-title":"Local computation with probabilities on graphical structures and their application to expert systems","volume":"50","author":"Lauritzen","year":"1988","journal-title":"Journal of the Royal Statistical Society, Series B"},{"issue":"1","key":"10.1016\/S1574-6526(06)80011-8_bib36","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","article-title":"Consistency in networks of relations","volume":"8","author":"Mackworth","year":"1977","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib37","doi-asserted-by":"crossref","DOI":"10.1016\/0004-3702(85)90041-4","article-title":"The complexity of some polynomial network consistency algorithms for constraint satisfaction problems","volume":"25","author":"Mackworth","year":"1985","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80011-8_bib38","series-title":"Computer Science Press, Rockville, MD","article-title":"The theory of relational databases","author":"Maier","year":"1983"},{"key":"10.1016\/S1574-6526(06)80011-8_bib39","series-title":"Bucket elimination and hypertree decompositions","author":"McMahan","year":"2004"},{"issue":"1\/2","key":"10.1016\/S1574-6526(06)80011-8_bib40","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1023\/A:1006303512524","article-title":"Resolution vs. search; two strategies for sat","volume":"24","author":"Rish","year":"2000","journal-title":"Journal of Automated Reasoning"},{"key":"10.1016\/S1574-6526(06)80011-8_bib41","series-title":"International Joint-conference of Artificial Intelligence (IJCAI05)","first-page":"1535","article-title":"Hypertree decomposition via branch-decomposition","author":"Samer","year":"2005"},{"key":"10.1016\/S1574-6526(06)80011-8_bib42","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1145\/1055558.1055587","article-title":"Weighted hypertree decompositions and optimal query plans","author":"Scarcello","year":"2004","journal-title":"PODS'04"},{"key":"10.1016\/S1574-6526(06)80011-8_bib43","series-title":"International Joint Conference on Artificial Intelligence (Ijcai-81)","first-page":"338","article-title":"A new method for solving constraint satisfaction problems","author":"Seidel","year":"1981"},{"key":"10.1016\/S1574-6526(06)80011-8_bib44","series-title":"Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence (UAI96)","first-page":"492","article-title":"Binary join trees","author":"Shenoy","year":"1996"},{"key":"10.1016\/S1574-6526(06)80011-8_bib45","series-title":"Fourteenth National Conference on Artificial Intelligence (AAAI'97)","first-page":"185","article-title":"A practical algorithm for finding optimal triangulations","author":"Shoiket","year":"1997"},{"issue":"3","key":"10.1016\/S1574-6526(06)80011-8_bib46","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1137\/0213035","article-title":"Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs","volume":"13","author":"Tarjan","year":"1984","journal-title":"SIAM Journal of Computation"}],"container-title":["Foundations of Artificial Intelligence","Handbook of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1574652606800118?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1574652606800118?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T02:51:28Z","timestamp":1761619888000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1574652606800118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9780444527264"],"references-count":46,"URL":"https:\/\/doi.org\/10.1016\/s1574-6526(06)80011-8","relation":{},"ISSN":["1574-6526"],"issn-type":[{"value":"1574-6526","type":"print"}],"subject":[],"published":{"date-parts":[[2006]]}}}