{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:23:37Z","timestamp":1772083417370,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_69","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"846-858","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Algebraic Properties of Valued Constraint Satisfaction Problem"],"prefix":"10.1007","author":[{"given":"Marcin","family":"Kozik","sequence":"first","affiliation":[]},{"given":"Joanna","family":"Ochremiak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"69_CR1","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Logical Methods in Computer Science 8(1) (2012)","DOI":"10.2168\/LMCS-8(1:7)2012"},{"key":"69_CR2","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1017\/S0305004100013463","volume":"31","author":"G Birkhoff","year":"1935","unstructured":"Birkhoff, G.: On the structure of abstract algebras. Proceedings of the Cambridge Philosophical Society 31, 433\u2013454 (1935)","journal-title":"Proceedings of the Cambridge Philosophical Society"},{"key":"69_CR3","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 Journal on Computing 34, 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"69_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. In: Proc. of the 18th Symposium on Logic in Computer Science, p. 321 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"issue":"1","key":"69_CR5","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"AA Bulatov","year":"2006","unstructured":"Bulatov, A.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":"69_CR6","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Logic 12(4), 24:1\u201324:66 (2011)","DOI":"10.1145\/1970398.1970400"},{"key":"69_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Automata, Languages and Programming","author":"AA Bulatov","year":"2000","unstructured":"Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 272\u2013282. Springer, Heidelberg (2000)"},{"key":"69_CR8","doi-asserted-by":"crossref","unstructured":"Burris, S., Sankappanavar, H.P.: A course in universal algebra. Graduate texts in mathematics. Springer (1981)","DOI":"10.1007\/978-1-4613-8130-3"},{"issue":"5","key":"69_CR9","doi-asserted-by":"publisher","first-page":"1915","DOI":"10.1137\/130906398","volume":"42","author":"DA Cohen","year":"2013","unstructured":"Cohen, D.A., Cooper, M.C., Creed, P., Jeavons, P.G., \u017divn\u00fd, S.: An algebraic theory of complexity for discrete optimization. SIAM J. Comput. 42(5), 1915\u20131939 (2013)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"69_CR10","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.artint.2006.04.002","volume":"170","author":"DA Cohen","year":"2006","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G., Krokhin, A.A.: The complexity of soft constraint satisfaction. Artif. Intell. 170(11), 983\u20131016 (2006)","journal-title":"Artif. Intell."},{"issue":"1","key":"69_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","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 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"69_CR12","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. Journal of Combinatorial Theory, Series B 48(1), 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"69_CR13","doi-asserted-by":"crossref","unstructured":"Huber, A., Krokhin, A., Powell, R.: Skew bisubmodularity and valued CSPs. In: Proc. SODA 2013, pp. 1296\u20131305. SIAM (2013)","DOI":"10.1137\/1.9781611973105.94"},{"issue":"4","key":"69_CR14","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 44(4), 527\u2013548 (1997)","journal-title":"J. ACM"},{"key":"69_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. Bulletin of the EATCS 113, 21\u201355 (2014)","journal-title":"Bulletin of the EATCS"},{"key":"69_CR16","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V., \u017divn\u00fd, S.: The complexity of conservative valued CSPs. J. ACM 60(2), 10:1\u201310:38 (2013)","DOI":"10.1145\/2450142.2450146"},{"key":"69_CR17","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. 410, 1629\u20131647 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"69_CR18","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. of the 10th ACM Symp. on Theory of Computing, STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"1","key":"69_CR19","doi-asserted-by":"publisher","first-page":"163","DOI":"10.2307\/1969039","volume":"47","author":"A Tarski","year":"1946","unstructured":"Tarski, A.: A remark on functionally free algebras. Annals of Mathematics 47(1), 163\u2013166 (1946)","journal-title":"Annals of Mathematics"},{"key":"69_CR20","doi-asserted-by":"crossref","unstructured":"Thapper, J., \u017divn\u00fd, S.: The complexity of finite-valued CSPs. In: Proc. of the 45th ACM Symp. on Theory of Computing, STOC 2013, pp. 695\u2013704 (2013)","DOI":"10.1145\/2488608.2488697"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_69","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:09:06Z","timestamp":1748459346000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_69"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_69","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}