{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:40:22Z","timestamp":1770972022031,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441205","type":"print"},{"value":"9783540461357","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46135-3_21","type":"book-chapter","created":{"date-parts":[[2007,5,15]],"date-time":"2007-05-15T05:59:47Z","timestamp":1179208787000},"page":"310-326","source":"Crossref","is-referenced-by-count":73,"title":["Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics"],"prefix":"10.1007","author":[{"given":"V\u00edctor","family":"Dalmau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,9,2]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. In Proc. 25th ACM Symp. on Theory of Computing, pages 226\u2013234, 1993.","DOI":"10.1145\/167088.167161"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proc. 9th ACM Symp. on Theory of Computing, pages 77\u201390, 1977.","DOI":"10.1145\/800105.803397"},{"issue":"1","key":"21_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0004-3702(92)90043-W","volume":"55","author":"R. Dechter","year":"1992","unstructured":"R. Dechter. From local to global consistency. Artificial Intelligence, 55(1):87\u2013107, May 1992.","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"21_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","volume":"113","author":"R. Dechter","year":"1999","unstructured":"R. Dechter. Bucket elimination: a unifying framework for reasoning. Artificial Intelligence, 113(1\u20132):41\u201385, 1999.","journal-title":"Artificial Intelligence"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parametrized Complexity. Springer-Verlag, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"R. Dechter and J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, pages 353\u2013366, 1989.","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"21_CR7","unstructured":"E.C Freuder. Complexity of k-tree structured constraint satisfaction problems. In Proc. AAAI-90, pages 4\u20139, 1990."},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. on Computing, 28:57\u2013104, 1998.","journal-title":"SIAM J. on Computing"},{"key":"21_CR9","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability-A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979."},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(92)90294-K","volume":"35","author":"W. Gutjahr","year":"1992","unstructured":"W. Gutjahr, E. Welzl, and G. Woeginger. Polynomial Graph Colorings. Discrete Appl. Math., 35:29\u201346, 1992.","journal-title":"Discrete Appl. Math."},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"P. Hell and J. Ne\u0161et\u0159il. On the complexity of H-coloring. Journal of Combinatorial Theory, Series B, 48:92\u2013110, 1990.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0012-365X(92)90282-K","volume":"109","author":"P. Hell","year":"1992","unstructured":"P. Hell and J. Ne\u0161et\u0159il. The core of a graph. Discrete Math., 109:117\u2013126, 1992.","journal-title":"Discrete Math."},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0166-218X(96)00099-6","volume":"70","author":"P. Hell","year":"1996","unstructured":"P. Hell, J. Nesetril, and X. Zhu. Complexity of Tree Homomorphism. Discrete Appl. Math., 70:23\u201336, 1996.","journal-title":"Discrete Appl. Math."},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"J. N. Hooker. Constraint satisfaction methods for generating valid cuts. In Advances in computational and stochastic optimization, logic programming, and heuristic studies, pages 1\u201330. Kluwer, 1997.","DOI":"10.1007\/978-1-4757-2807-1_1"},{"key":"21_CR15","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86\u2013104, 1986.","journal-title":"Information and Control"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"issue":"1\u20132","key":"21_CR17","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"P. Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200(1\u20132):185\u2013204, 1998.","journal-title":"Theoretical Computer Science"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. On the expressive power of Datalog: tools and a case study. Journal of Computer and System Sciences, 51(1):110\u2013134, August 1995.","DOI":"10.1006\/jcss.1995.1055"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Ph.G. Kolaitis and M. Y. Vardi. Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences, pages 302\u2013332, 2000.","DOI":"10.1006\/jcss.2000.1713"},{"key":"21_CR20","unstructured":"Ph.G. Kolaitis and M. Y. Vardi. A game-theoretic approach to constraint satisfaction. In Proc. of the 17th Nat. Conf. on Artificial Intelligence (A A AI 2000), pages 175\u2013181, 2000."},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer. The complexity of satisfiability problems. In Proc. 10th ACM Symp. on Theory of Computing, pages 216\u2013226, 1978.","DOI":"10.1145\/800133.804350"},{"key":"21_CR22","unstructured":"J. D. Ullman. Database and Knowledge-Base Systems, Volumes I and II. Computer Science Press, 1989."},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. The complexity of relational query languages. In Proc. 14th ACM Symp. on Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. On the complexity of bounded-variable queries. In Proc. 14th ACM Symp. on Principles of Database Systems, pages 266\u201376, 1995.","DOI":"10.1145\/212433.212474"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming - CP 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46135-3_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T00:25:22Z","timestamp":1556411122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46135-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441205","9783540461357"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-46135-3_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002]]}}}