{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:33:15Z","timestamp":1726410795149},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662489703"},{"type":"electronic","value":"9783662489710"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48971-0_48","type":"book-chapter","created":{"date-parts":[[2015,11,26]],"date-time":"2015-11-26T04:00:57Z","timestamp":1448510457000},"page":"566-577","source":"Crossref","is-referenced-by-count":2,"title":["Effectiveness of Structural Restrictions for Hybrid CSPs"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Kolmogorov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Rol\u00ednek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rustem","family":"Takhanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,27]]},"reference":[{"issue":"3","key":"48_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K Appel","year":"1977","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable. Part i: discharging. Illinois J. Math. 21(3), 429\u2013490 (1977)","journal-title":"Illinois J. Math."},{"key":"48_CR2","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik. M.: New conditions for Taylor varieties and CSP. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11\u201314 July 2010, Edinburgh, UK, pp. 100\u2013109 (2010)","DOI":"10.1109\/LICS.2010.34"},{"issue":"5","key":"48_CR3","doi-asserted-by":"publisher","first-page":"1782","DOI":"10.1137\/070708093","volume":"38","author":"L Barto","year":"2009","unstructured":"Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38(5), 1782\u20131802 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"48_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"key":"48_CR5","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Logic, 12(4) (2011). Article 24","DOI":"10.1145\/1970398.1970400"},{"issue":"3","key":"48_CR6","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"48_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-642-40627-0_17","volume-title":"Principles and Practice of Constraint Programming","author":"J Bul\u00edn","year":"2013","unstructured":"Bul\u00edn, J., Deli\u0107, D., Jackson, M., Niven, T.: On the reduction of the CSP dichotomy conjecture to digraphs. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 184\u2013199. Springer, Heidelberg (2013)"},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151\u2013158. ACM, New York (1971)","DOI":"10.1145\/800157.805047"},{"issue":"9\u201310","key":"48_CR9","doi-asserted-by":"publisher","first-page":"1555","DOI":"10.1016\/j.artint.2011.02.003","volume":"175","author":"MC Cooper","year":"2011","unstructured":"Cooper, M.C., \u017divn\u00fd, S.: Hybrid tractability of valued constraint problems. Artif. Intell. 175(9\u201310), 1555\u20131569 (2011)","journal-title":"Artif. Intell."},{"issue":"1","key":"48_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"48_CR11","doi-asserted-by":"publisher","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"D Geiger","year":"1968","unstructured":"Geiger, D.: Closed systems of functions and predicates. Pacific J. Math. 27(1), 95\u2013100 (1968)","journal-title":"Pacific J. Math."},{"issue":"1","key":"48_CR12","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1), 1:1\u20131:24 (2007)","journal-title":"J. ACM"},{"key":"48_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York (1988)"},{"issue":"1","key":"48_CR14","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of h-coloring. J. Comb. Theory, Series B 48(1), 92\u2013110 (1990)","journal-title":"J. Comb. Theory, Series B"},{"key":"48_CR15","first-page":"21","volume":"113","author":"P Jeavons","year":"2014","unstructured":"Jeavons, P., Krokhin, A., \u017divn\u00fd, S.: The complexity of valued constraint satisfaction. Bull. EATCS 113, 21\u201355 (2014)","journal-title":"Bull. EATCS"},{"issue":"1\u20132","key":"48_CR16","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theor. Comput. Sci. 200(1\u20132), 185\u2013204 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"48_CR17","unstructured":"J\u00e9gou, P.: Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems. In: AAAI, pp. 731\u2013736 (1993)"},{"key":"48_CR18","unstructured":"Kolmogorov, V., Rol\u00ednek, M., Takhanov, R.: Effectiveness of structural restrictions for hybrid CSPs (2015). \n                      arXiv1504.07067"},{"key":"48_CR19","unstructured":"Kuznetsov, A.V.: Algebra of logic and their generalizations. In: Mathematics in USSR for 40 years, vol. 1, pp. 105\u2013115. Fizmatgiz Moscow (1959)"},{"issue":"3\u20134","key":"48_CR20","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s00012-008-2122-9","volume":"59","author":"M Mar\u00f3ti","year":"2008","unstructured":"Mar\u00f3ti, M., McKenzie, R.: Existence theorems for weakly symmetric operations. Algebra Universalis 59(3\u20134), 463\u2013489 (2008)","journal-title":"Algebra Universalis"},{"key":"48_CR21","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1007\/978-3-642-55566-4_29","volume-title":"Discrete and Computational Geometry","author":"J Ne\u0161et\u0159il","year":"2003","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Colorings and homomorphisms of minor closed classes. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 25, pp. 651\u2013664. Springer, Heidelberg (2003)"},{"key":"48_CR22","doi-asserted-by":"crossref","unstructured":"Post, E.L.: On The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, Princeton (1941)","DOI":"10.1515\/9781400882366"},{"key":"48_CR23","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"1\u20132","key":"48_CR24","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s00012-010-0082-3","volume":"64","author":"MH Siggers","year":"2010","unstructured":"Siggers, M.H.: A strong Mal\u2019cev condition for locally finite varieties omitting the unary type. Algebra Universalis 64(1\u20132), 15\u201320 (2010)","journal-title":"Algebra Universalis"},{"key":"48_CR25","unstructured":"Swarts, J.: The complexity of digraph homomorphisms: Local tournaments, injective homomorphisms and polymorphisms. Ph. D. thesis, University of Victoria, Canada (2008)"},{"key":"48_CR26","unstructured":"Takhanov, R.S.: A dichotomy theorem for the general minimum cost homomorphism problem. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 657\u2013668 (2010)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48971-0_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T17:50:40Z","timestamp":1559325040000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48971-0_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489703","9783662489710"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48971-0_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}