{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T01:17:19Z","timestamp":1772846239687,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540310006","type":"print"},{"value":"9783540314684","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11604686_1","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:02:01Z","timestamp":1133794921000},"page":"1-15","source":"Crossref","is-referenced-by-count":39,"title":["Hypertree Decompositions: Structure, Algorithms, and Applications"],"prefix":"10.1007","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[]},{"given":"Nysret","family":"Musliu","sequence":"additional","affiliation":[]},{"given":"Marko","family":"Samer","sequence":"additional","affiliation":[]},{"given":"Francesco","family":"Scarcello","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1002\/jgt.20025","volume":"47","author":"I. Adler","year":"2004","unstructured":"Adler, I.: Marshals, monotone marshals, and hypertree width. Journal of Graph Theory\u00a047, 275\u2013296 (2004)","journal-title":"Journal of Graph Theory"},{"key":"1_CR2","unstructured":"Adler, I., Gottlob, G., Grohe, M.: Hypertree-width and related hypergraph invariants. Manuscript, submitted for publication, available from the authors"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational databases. In: Proc. STOC 1977, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"key":"1_CR4","unstructured":"Cohen, D.A., Jeavons, P.G., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In: Proc. IJCAI 2005, pp. 72\u201377 (2005)"},{"key":"1_CR5","first-page":"276","volume-title":"Encyclopedia of Artificial Intelligence","author":"R. Dechter","year":"1992","unstructured":"Dechter, R.: Constraint networks. In: Encyclopedia of Artificial Intelligence, 2nd edn., pp. 276\u2013285. Wiley & Sons, Chichester (1992)","edition":"2"},{"issue":"1","key":"1_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R. Dechter","year":"1987","unstructured":"Dechter, R., Pearl, J.: Network-based heuristics for constraint satisfaction problems. Artificial Intelligence\u00a034(1), 1\u201338 (1987)","journal-title":"Artificial Intelligence"},{"issue":"3","key":"1_CR7","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R. Dechter","year":"1989","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artificial Intelligence\u00a038(3), 353\u2013366 (1989)","journal-title":"Artificial Intelligence"},{"key":"1_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"4","key":"1_CR9","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1145\/4221.4225","volume":"32","author":"E.C. Freuder","year":"1985","unstructured":"Freuder, E.C.: A sufficient condition for backtrack bounded search. Journal of the ACM\u00a032(4), 755\u2013761 (1985)","journal-title":"Journal of the ACM"},{"key":"#cr-split#-1_CR10.1","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: Pure Nash equilibria: Hard and easy games. Journal of Artificial Intelligence Research, JAIR (2005) (To appear);","DOI":"10.1613\/jair.1683"},{"key":"#cr-split#-1_CR10.2","unstructured":"Preliminary version In: Proc. TARK 2003 (2003)"},{"issue":"3","key":"1_CR11","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/382780.382783","volume":"48","author":"G. Gottlob","year":"2001","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. Journal of the ACM\u00a048(3), 431\u2013498 (2001); Preliminary version in: Proc. FOCS 1998 (1998)","journal-title":"Journal of the ACM"},{"issue":"1-2","key":"1_CR12","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1016\/S0304-3975(01)00108-6","volume":"270","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Computing LOGCFL certificates. Theoretical Computer Science\u00a0270(1-2), 761\u2013777 (2002); Preliminary version In: Proc. ICALP 1999 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"1_CR13","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. Journal of Computer and System Sciences (JCSS)\u00a064(3), 579\u2013627 (2002); Preliminary version In: Proc. PODS 1999, (1999)","journal-title":"Journal of Computer and System Sciences (JCSS)"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-48309-8_1","volume-title":"Database and Expert Systems Applications","author":"G. Gottlob","year":"1999","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: On tractable queries and constraints. In: Bench-Capon, T.J.M., Soda, G., Tjoa, A.M. (eds.) DEXA 1999. LNCS, vol.\u00a01677, pp. 1\u201315. Springer, Heidelberg (1999)"},{"issue":"2","key":"1_CR15","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. Artificial Intelligence\u00a0124(2), 243\u2013282 (2000); Preliminary version In: Proc. IJCAI 1999 (1999)","journal-title":"Artificial Intelligence"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Robbers, marshals, and guards: Game-theoretic and logical characterizations of hypertree width. In: Proc. PODS 2001, pp. 195\u2013206 (2001)","DOI":"10.1145\/375551.375579"},{"issue":"2","key":"1_CR17","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/S0097539701396807","volume":"33","author":"G. Gottlob","year":"2004","unstructured":"Gottlob, G., Pichler, R.: Hypergraphs in model checking: Acyclicity and hypertree-width versus clique-width. Siam Journal of Computing\u00a033(2), 351\u2013378 (2004)","journal-title":"Siam Journal of Computing"},{"key":"1_CR18","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, 57\u201389 (1994)","journal-title":"Artificial Intelligence"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Gyssens, M., Paredaens, J.: A decomposition methodology for cyclic databases. In: Advances in Database Theory, vol.\u00a02, pp. 85\u2013122 (1984)","DOI":"10.1007\/978-1-4615-9385-0_4"},{"key":"1_CR20","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 (JCSS)\u00a061, 302\u2013332 (2000)","journal-title":"Journal of Computer and System Sciences (JCSS)"},{"key":"1_CR21","unstructured":"Korimort, T.: Constraint satisfaction problems \u2013 Heuristic decomposition. PhD thesis, Vienna University of Technology (April 2003)"},{"key":"1_CR22","volume-title":"The theory of relational databases","author":"D. Maier","year":"1986","unstructured":"Maier, D.: The theory of relational databases. Computer Science Press, Rockville (1986)"},{"key":"1_CR23","unstructured":"McMahan, B.: Bucket eliminiation and hypertree decompositions. Implementation report, Institute of Information Systems (DBAI), TU Vienna (2004)"},{"key":"1_CR24","unstructured":"Pearson, J., Jeavons, P.G.: A survey of tractable constraint satisfaction problems. Technical report CSD-TR-97-15, Royal Halloway University of London (1997)"},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1017\/CBO9780511662119.006","volume-title":"Surveys in Combinatorics","author":"B. Reed","year":"1997","unstructured":"Reed, B.: Tree width and tangles: A new connectivity measure and some applications. In: Surveys in Combinatorics. LNCS, vol.\u00a0241, pp. 87\u2013162. Cambridge University Press, Cambridge (1997)"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series\u00a0B\u00a052, 153\u2013190 (1991)","journal-title":"Journal of Combinatorial Theory, Series\u00a0B"},{"issue":"2","key":"1_CR27","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W.L. Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. Journal of Computer and System Sciences (JCSS)\u00a021(2), 218\u2013235 (1980)","journal-title":"Journal of Computer and System Sciences (JCSS)"},{"key":"1_CR28","unstructured":"Samer, M.: Hypertree-decomposition via branch-decomposition. In: Proc. IJCAI 2005, pp. 1535\u20131536 (2005)"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P.D. Seymour","year":"1993","unstructured":"Seymour, P.D., Thomas, R.: Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B\u00a058, 22\u201333 (1993)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"1_CR30","unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: Proc. VLDB 1981, pp. 82\u201394 (1981)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11604686_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:14Z","timestamp":1619507054000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11604686_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540310006","9783540314684"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11604686_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}