{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:22:02Z","timestamp":1726410122008},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_6","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"42-54","source":"Crossref","is-referenced-by-count":0,"title":["Balanced Queries: Divide and Conquer"],"prefix":"10.1007","author":[{"given":"Dmitri","family":"Akatov","sequence":"first","affiliation":[]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"http:\/\/benner.dbai.tuwien.ac.at\/staff\/gottlob\/DAGG-MFCS10.pdf"},{"key":"6_CR2","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1994","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley, Reading (November 1994)"},{"issue":"4","key":"6_CR3","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(4), 275\u2013296 (2004)","journal-title":"Journal of Graph Theory"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Beigel, R., Fu, B.: Molecular computing, bounded nondeterminism, and efficient recursion. In: Proceedings of the 24th International Colloquium on Automata, Languages, and Programming, vol.\u00a025, pp. 816\u2013826 (1998)","DOI":"10.1007\/3-540-63165-8_234"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1137\/S0097539793258295","volume":"26","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On the amount of nondeterminism and the power of verifying. SIAM Journal on Computing\u00a026, 311\u2013320 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/800105.803397","volume-title":"STOC 1977: Proceedings of the ninth annual ACM symposium on Theory of computing","author":"A.K. Chandra","year":"1977","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC 1977: Proceedings of the ninth annual ACM symposium on Theory of computing, pp. 77\u201390. ACM, New York (1977)"},{"key":"6_CR7","first-page":"72","volume-title":"IJCAI 2005: Proceedings of the 19th international joint conference on Artificial intelligence","author":"D. Cohen","year":"2005","unstructured":"Cohen, D., Jeavons, P., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In: IJCAI 2005: Proceedings of the 19th international joint conference on Artificial intelligence, pp. 72\u201377. Morgan Kaufmann Publishers Inc., San Francisco (2005)"},{"issue":"1","key":"6_CR8","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1145\/321371.321385","volume":"14","author":"S. Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: Stack automata and compiling. J. ACM\u00a014(1), 172\u2013201 (1967)","journal-title":"J. ACM"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Goldsmith, J., Levy, M.A., Mundhenk, M.: Limited nondeterminism (1996)","DOI":"10.1145\/235767.235769"},{"issue":"2","key":"6_CR10","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)","journal-title":"Artificial Intelligence"},{"issue":"3","key":"6_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. J. ACM\u00a048(3), 431\u2013498 (2001)","journal-title":"J. ACM"},{"issue":"3","key":"6_CR12","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\u00a064(3), 579\u2013627 (2002)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"6_CR13","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, N., Scarcello, F.: Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. J. Comput. Syst. Sci.\u00a066(4), 775\u2013808 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1265530.1265533","volume-title":"PODS 2007: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems","author":"G. Gottlob","year":"2007","unstructured":"Gottlob, G., Miklos, Z., Schwentick, T.: Generalized hypertree decompositions: Np-hardness and tractable variants. In: PODS 2007: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 13\u201322. ACM Press, New York (2007)"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Samer, M.: A backtracking-based algorithm for hypertree decomposition. J. Exp. Algorithmics\u00a013 (2009)","DOI":"10.1145\/1412228.1412229"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/1109557.1109590","volume-title":"SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm","author":"M. Grohe","year":"2006","unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 289\u2013298. ACM, New York (2006)"},{"issue":"3","key":"6_CR17","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P. Hlineny","year":"2007","unstructured":"Hlineny, P., Oum, S.-i., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. The Computer Journal\u00a051(3), 326\u2013362 (2007)","journal-title":"The Computer Journal"},{"issue":"2","key":"6_CR18","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(71)80029-6","volume":"5","author":"O.H. Ibarra","year":"1971","unstructured":"Ibarra, O.H.: Characterizations of some tape and time complexity classes of turing machines in terms of multihead and auxiliary stack automata. Journal of Computer and System Sciences\u00a05(2), 88\u2013117 (1971)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"6_CR19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A. Mackworth","year":"1977","unstructured":"Mackworth, A.: Consistency in networks of relations. Artificial Intelligence\u00a08(1), 99\u2013118 (1977)","journal-title":"Artificial Intelligence"},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(85)90068-4","volume":"41","author":"B. Monien","year":"1985","unstructured":"Monien, B., Sudborough, I.H.: Bandwidth constrained np-complete problems. Theoretical Computer Science\u00a041, 141\u2013167 (1985)","journal-title":"Theoretical Computer Science"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1145\/1060590.1060647","volume-title":"STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 376\u2013385. ACM, New York (2005)"},{"issue":"3","key":"6_CR22","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.: Graph minors. ii. algorithmic aspects of tree-width. Journal of Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"6_CR23","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\u00a021(2), 218\u2013235 (1980)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"6_CR24","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P. Seymour","year":"1993","unstructured":"Seymour, P., Thomas, R.: Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B\u00a058(1), 22\u201333 (1993)","journal-title":"Journal of Combinatorial Theory, Series B"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:51Z","timestamp":1606186911000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}