{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:05:47Z","timestamp":1740096347262,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642406263"},{"type":"electronic","value":"9783642406270"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40627-0_17","type":"book-chapter","created":{"date-parts":[[2013,9,7]],"date-time":"2013-09-07T03:11:01Z","timestamp":1378523461000},"page":"184-199","source":"Crossref","is-referenced-by-count":6,"title":["On the Reduction of the CSP Dichotomy Conjecture to Digraphs"],"prefix":"10.1007","author":[{"given":"Jakub","family":"Bul\u00edn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dejan","family":"Deli\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcel","family":"Jackson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Todd","family":"Niven","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"17_CR1","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1016\/j.ejc.2007.11.004","volume":"29","author":"A. Atserias","year":"2008","unstructured":"Atserias, A.: On digraph coloring problems and treewidth duality. European J. Combin.\u00a029(4), 796\u2013820 (2008), \n                    \n                      http:\/\/dx.doi.org\/10.1016\/j.ejc.2007.11.004","journal-title":"European J. Combin."},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1109\/FOCS.2009.32","volume-title":"2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)","author":"L. Barto","year":"2009","unstructured":"Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 595\u2013603. IEEE Computer Soc., Los Alamitos (2009), \n                    \n                      http:\/\/dx.doi.org\/10.1109\/FOCS.2009.32"},{"key":"17_CR3","doi-asserted-by":"crossref","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.\u00a038(5), 1782\u20131802 (2008\/2009), \n                    \n                      http:\/\/dx.doi.org\/10.1137\/070708093","DOI":"10.1137\/070708093"},{"issue":"3","key":"17_CR4","doi-asserted-by":"publisher","first-page":"1445","DOI":"10.1090\/S0002-9947-09-04874-0","volume":"362","author":"J. Berman","year":"2010","unstructured":"Berman, J., Idziak, P., Markovi\u0107, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers. Trans. Amer. Math. Soc.\u00a0362(3), 1445\u20131473 (2010), \n                    \n                      http:\/\/dx.doi.org\/10.1090\/S0002-9947-09-04874-0","journal-title":"Trans. Amer. Math. Soc."},{"issue":"3","key":"17_CR5","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput.\u00a034(3), 720\u2013742 (2005), \n                    \n                      http:\/\/dx.doi.org\/10.1137\/S0097539700376676","journal-title":"SIAM J. Comput."},{"issue":"1","key":"17_CR6","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM\u00a053(1), 66\u2013120 (2006), \n                    \n                      http:\/\/dx.doi.org\/10.1145\/1120582.1120584","journal-title":"J. ACM"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-540-48085-3_12","volume-title":"Principles and Practice of Constraint Programming \u2013 CP\u201999","author":"V. Dalmau","year":"1999","unstructured":"Dalmau, V., Pearson, J.: Closure functions and width 1 problems. In: Jaffar, J. (ed.) CP 1999. LNCS, vol.\u00a01713, pp. 159\u2013173. Springer, Heidelberg (1999)"},{"key":"17_CR8","doi-asserted-by":"crossref","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.\u00a028(1), 57\u2013104 (electronic) (1999), \n                    \n                      http:\/\/dx.doi.org\/10.1137\/S0097539794266766","DOI":"10.1137\/S0097539794266766"},{"issue":"1","key":"17_CR9","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. Combin. Theory Ser. B\u00a048(1), 92\u2013110 (1990), http:\/\/dx.doi.org\/10.1016\/0095-8956(90)90132-J","journal-title":"J. Combin. Theory Ser. B"},{"key":"17_CR10","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and homomorphisms","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and homomorphisms. Oxford Lecture Series in Mathematics and its Applications, vol.\u00a028. Oxford University Press, Oxford (2004), \n                    \n                      http:\/\/dx.doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001"},{"issue":"7","key":"17_CR11","doi-asserted-by":"publisher","first-page":"3023","DOI":"10.1137\/090775646","volume":"39","author":"P. Idziak","year":"2010","unstructured":"Idziak, P., Markovi\u0107, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebras with few subpowers. SIAM J. Comput.\u00a039(7), 3023\u20133037 (2010), \n                    \n                      http:\/\/dx.doi.org\/10.1137\/090775646","journal-title":"SIAM J. Comput."},{"key":"17_CR12","unstructured":"Jackson, M., Kowalski, T., Niven, T.: Digraph related constructions and the complexity of digraph homomorphism problems. arXiv:1304.4986 [math.CO] (2013)"},{"issue":"4","key":"17_CR13","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. J. ACM\u00a044(4), 527\u2013548 (1997), \n                    \n                      http:\/\/dx.doi.org\/10.1145\/263867.263489","journal-title":"J. ACM"},{"issue":"3","key":"17_CR14","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1016\/j.ejc.2010.11.002","volume":"32","author":"A. Kazda","year":"2011","unstructured":"Kazda, A.: Maltsev digraphs have a majority polymorphism. European J. Combin.\u00a032(3), 390\u2013397 (2011), \n                    \n                      http:\/\/dx.doi.org\/10.1016\/j.ejc.2010.11.002","journal-title":"European J. Combin."},{"key":"17_CR15","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. Assoc. Comput. Mach.\u00a022, 155\u2013171 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"18","key":"17_CR16","doi-asserted-by":"publisher","first-page":"1629","DOI":"10.1016\/j.tcs.2008.12.048","volume":"410","author":"B. Larose","year":"2009","unstructured":"Larose, B., Tesson, P.: Universal algebra and hardness results for constraint satisfaction problems. Theor. Comput. Sci.\u00a0410(18), 1629\u20131647 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3-4","key":"17_CR17","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\u00a059(3-4), 463\u2013489 (2008), \n                    \n                      http:\/\/dx.doi.org\/10.1007\/s00012-008-2122-9","journal-title":"Algebra Universalis"},{"key":"17_CR18","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Information Sci.\u00a07, 95\u2013132 (1974)","journal-title":"Information Sci."},{"key":"17_CR19","first-page":"216","volume-title":"Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978)","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), pp. 216\u2013226. ACM, New York (1978)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40627-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T22:10:01Z","timestamp":1558044601000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40627-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642406263","9783642406270"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40627-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}