{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T17:42:10Z","timestamp":1761932530208,"version":"build-2065373602"},"reference-count":28,"publisher":"IEEE Computer. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2003.1238228","type":"proceedings-article","created":{"date-parts":[[2004,3,1]],"date-time":"2004-03-01T21:26:50Z","timestamp":1078176410000},"page":"552-561","source":"Crossref","is-referenced-by-count":16,"title":["The complexity of homomorphism and constraint satisfaction problems seen from the other side"],"prefix":"10.1109","author":[{"given":"M.","family":"Grohe","sequence":"first","affiliation":[]}],"member":"263","reference":[{"key":"19","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"17","first-page":"657","article-title":"When is the evaluation of conjunctive queries tractable","author":"grohe","year":"2001","journal-title":"Proc 29th ACM Symp on Theory of Computing"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303979"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"14","first-page":"4","article-title":"Complexity of k-tree structured constraint satisfaction problems","author":"freuder","year":"1990","journal-title":"Proc AAAI-90"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1055"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275511"},{"key":"23","first-page":"12","article-title":"On limited nondeterminism and the complexity of the VC-dimension","author":"papadimitriou","year":"1993","journal-title":"Proceedings of the 25th ACM Symposium on Theory of Computing"},{"key":"24","first-page":"18","article-title":"Finding minimally weighted subgraphs","author":"plehn","year":"1990","journal-title":"Graph-Theoretic Concepts in Computer Science WG '90 Volume 484 of Lecture Notes in Computer Science"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"28","first-page":"82","article-title":"Algorithms for acyclic database schemes","author":"yannakakis","year":"1981","journal-title":"Proc 5th Int Conf Very Large Data Bases"},{"key":"3","first-page":"272","article-title":"Constraint satisfaction problems and finite algebras","author":"bulatov","year":"2000","journal-title":"Proceedings of the 27th International Colloquium on Automata Languages and Programming Volume 1853 of Lecture Notes in Computer Science"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","author":"downey","year":"1999","journal-title":"Parameterized Complexity"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00034-Z"},{"key":"7","first-page":"310","article-title":"Constraint satisfaction, bounded treewidth, and finite-variable logics","author":"dalmau","year":"2002","journal-title":"Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming Volume 2470 of Lecture Notes in Computer Science"},{"key":"6","first-page":"56","article-title":"Conjunctive query containment revisited","author":"chekuri","year":"1997","journal-title":"Proceedings of the 5th International Conference on Database Theory Volume 1186 of Lecture Notes in Computer Science"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380868"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"}],"event":{"name":"44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003","acronym":"SFCS-03","location":"Cambridge, MA, USA"},"container-title":["44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8767\/27770\/01238228.pdf?arnumber=1238228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T00:05:27Z","timestamp":1497571527000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1238228\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":28,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2003.1238228","relation":{},"subject":[]}}