{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:26:28Z","timestamp":1725560788887},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540292388"},{"type":"electronic","value":"9783540320500"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11564751_15","type":"book-chapter","created":{"date-parts":[[2005,10,18]],"date-time":"2005-10-18T13:31:28Z","timestamp":1129642288000},"page":"167-181","source":"Crossref","is-referenced-by-count":29,"title":["Beyond Hypertree Width: Decomposition Methods Without Decompositions"],"prefix":"10.1007","author":[{"given":"Hubie","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V\u00edctor","family":"Dalmau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Adler, I., Gottlob, G., Grohe, M.: Hypertree-width and related hypergraph invariants (In preparation)"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-540-30201-8_9","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2004","author":"A. Atserias","year":"2004","unstructured":"Atserias, A., Kolaitis, P.G., Vardi, M.Y.: Constraint propagation as a proof system. In: Wallace, M. (ed.) CP 2004. LNCS, vol.\u00a03258, pp. 77\u201391. Springer, Heidelberg (2004)"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-30577-4_1","volume-title":"SOFSEM 2005: Theory and Practice of Computer Science","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L.: Discovering treewidth. In: Vojt\u00e1\u0161, P., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) SOFSEM 2005. LNCS, vol.\u00a03381, pp. 1\u201316. Springer, Heidelberg (2005)"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings of 43rd IEEE Symposium on Foundations of Computer Science, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"#cr-split#-15_CR5.1","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: Proceedings of 18th IEEE Symposium on Logic in Computer Science (LICS 2003), pp. 321???330 (2003);","DOI":"10.1109\/LICS.2003.1210072"},{"key":"#cr-split#-15_CR5.2","unstructured":"Extended version appears as Oxford University technical report PRG-RR???03-01"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Chen, H., Dalmau, V.: From pebble games to tractability: An ambidextrous consistency algorithm for quantified constraint satisfaction (2005) (Manuscript)","DOI":"10.1007\/11538363_17"},{"key":"15_CR7","unstructured":"Cohen, D., Jeavons, P., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. To appear in IJCAI 2005 (2005)"},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-46135-3_21","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, p. 310. Springer, Heidelberg (2002)"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. In: Artificial Intelligence, pp. 353\u2013366 (1989)","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"15_CR10","unstructured":"Freuder, E.: Complexity of k-tree structured constraint satisfaction problems. In: AAAI 1990 (1990)"},{"issue":"3","key":"15_CR11","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, L., Scarcello, F.: Hypertree decomposition and tractable queries. Journal of Computer and System Sciences\u00a064(3), 579\u2013627 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1016\/S0022-0000(03)00030-8","volume":"66","author":"G. Gottlob","year":"2003","unstructured":"Gottlob, G., Leone, L., Scarcello, F.: Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. Journal of Computer and System Sciences\u00a066, 775\u2013808 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"15_CR13","doi-asserted-by":"publisher","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.: A comparison of structural csp decomposition methods. Artif. Intell.\u00a0124(2), 243\u2013282 (2000)","journal-title":"Artif. Intell."},{"issue":"3","key":"15_CR14","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/382780.382783","volume":"43","author":"G. Gottlob","year":"2001","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. Journal of the ACM\u00a043(3), 431\u2013498 (2001)","journal-title":"Journal of the ACM"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. In: FOCS 2003, pp. 552\u2013561 (2003)","DOI":"10.1109\/SFCS.2003.1238228"},{"issue":"1","key":"15_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","volume":"66","author":"M. Gyssens","year":"1994","unstructured":"Gyssens, M., Jeavons, P.G., Cohen, D.A.: Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence\u00a066(1), 57\u201389 (1994)","journal-title":"Artificial Intelligence"},{"key":"15_CR17","first-page":"85","volume-title":"Advances in Database Theory","author":"M. Gysssens","year":"1984","unstructured":"Gysssens, M., Paradaens, J.: A decomposition methodology for cyclic databases. In: Advances in Database Theory, vol.\u00a02, pp. 85\u2013122. Plenum Press, New York (1984)"},{"issue":"1","key":"15_CR18","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/jcss.1995.1055","volume":"51","author":"P.G. Kolaitis","year":"1995","unstructured":"Kolaitis, P.G., Vardi, M.Y.: On the expressive power of Datalog: tools and a case study. Journal of Computer and System Sciences\u00a051(1), 110\u2013134 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P.G. Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences\u00a061, 302\u2013332 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR20","unstructured":"Kolaitis, P.G., Vardi, M.Y.: A game-theoretic approach to constraint satisfaction. In: Proceedings 17th National (US) Conference on Artificial Intellignece, AAAI 2000, pp. 175\u2013181 (2000)"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming - CP 2005"],"original-title":[],"link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/11564751_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T10:13:23Z","timestamp":1586513603000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/10.1007\/11564751_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540292388","9783540320500"],"references-count":22,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/11564751_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}