{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:19Z","timestamp":1792111459688,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":16,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_747","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:32:23Z","timestamp":1553095943000},"page":"366-369","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity Dichotomies for Counting Graph Homomorphisms"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"2","key":"747_CR3372","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"A Bulatov","year":"2005","unstructured":"Bulatov A, Grohe M (2005) The complexity of partition functions. Theor Comput Sci 348(2):148\u2013186","journal-title":"Theor Comput Sci"},{"issue":"3","key":"747_CR3373","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/110840194","volume":"42","author":"JY Cai","year":"2013","unstructured":"Cai JY, Chen X, Lu P (2013) Graph homomorphisms with complex values: a dichotomy theorem. SIAM J Comput 42(3):924\u20131029","journal-title":"SIAM J Comput"},{"key":"747_CR3374","doi-asserted-by":"crossref","first-page":"179","DOI":"10.4064\/aa-16-2-179-194","volume":"16","author":"L Carlitz","year":"1969","unstructured":"Carlitz L (1969) Kloosterman sums and finite field extensions. Acta Arith 16:179\u2013193","journal-title":"Acta Arith"},{"key":"747_CR3375","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity classifications of boolean constraint satisfaction problems","author":"N Creignou","year":"2001","unstructured":"Creignou N, Khanna S, Sudan M (2001) Complexity classifications of boolean constraint satisfaction problems. SIAM monographs on discrete mathematics and applications. Society for Industrial and Applied Mathematics, Philadelphia"},{"issue":"3\u20134","key":"747_CR3376","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"M Dyer","year":"2000","unstructured":"Dyer M, Greenhill C (2000) The complexity of counting graph homomorphisms. Random Struct Algorithms 17(3\u20134):260\u2013289","journal-title":"Random Struct Algorithms"},{"key":"747_CR3377","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1090\/S0894-0347-06-00529-7","volume":"20","author":"M Freedman","year":"2007","unstructured":"Freedman M, Lov\u00e1sz L, Schrijver A (2007) Reflection positivity, rank connectivity, and homomorphism of graphs. J Am Math Soc 20:37\u201351","journal-title":"J Am Math Soc"},{"issue":"7","key":"747_CR3378","doi-asserted-by":"publisher","first-page":"3336","DOI":"10.1137\/090757496","volume":"39","author":"L Goldberg","year":"2010","unstructured":"Goldberg L, Grohe M, Jerrum M, Thurley M (2010) A complexity dichotomy for partition functions with mixed signs. SIAM J Comput 39(7):3336\u20133402","journal-title":"SIAM J Comput"},{"key":"747_CR3379","doi-asserted-by":"crossref","unstructured":"Grohe M, Thurley M (2011) Counting homomorphisms and partition functions. In: Grohe M, Makowsky J (eds) Model theoretic methods in finite combinatorics. Contemporary mathematics, vol\u00a0558. American Mathematical Society, Providence","DOI":"10.1090\/conm\/558"},{"issue":"1","key":"747_CR3380","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 (1990) On the complexity of H-coloring. J Comb Theory Ser B 48(1):92\u2013110","journal-title":"J Comb Theory Ser B"},{"issue":"1","key":"747_CR3381","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R Ladner","year":"1975","unstructured":"Ladner R (1975) On the structure of polynomial time reducibility. J ACM 22(1):155\u2013171","journal-title":"J ACM"},{"key":"747_CR3382","volume-title":"Finite fields. Encyclopedia of mathematics and its applications","author":"R Lidl","year":"1997","unstructured":"Lidl R, Niederreiter H (1997) Finite fields. Encyclopedia of mathematics and its applications, vol\u00a020. Cambridge University Press, Cambridge"},{"key":"747_CR3383","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/0607036","volume":"7","author":"N Linial","year":"1986","unstructured":"Linial N (1986) Hard enumeration problems in geometry and combinatorics. SIAM J Algebraic Discret Methods 7:331\u2013335","journal-title":"SIAM J Algebraic Discret Methods"},{"key":"747_CR3384","first-page":"216","volume-title":"Proceedings of the 10th annual ACM symposium on theory of computing","author":"T Schaefer","year":"1978","unstructured":"Schaefer T (1978) The complexity of satisfiability problems. In: Proceedings of the 10th annual ACM symposium on theory of computing, San Diego, California, pp\u00a0216\u2013226"},{"key":"747_CR3385","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S Vadhan","year":"2002","unstructured":"Vadhan S (2002) The complexity of counting in sparse, regular, and planar graphs. SIAM J Comput 31:398\u2013427","journal-title":"SIAM J Comput"},{"key":"747_CR3386","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L Valiant","year":"1979","unstructured":"Valiant L (1979) The complexity of computing the permanent. Theor Comput Sci 8:189\u2013201","journal-title":"Theor Comput Sci"},{"key":"747_CR3387","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L Valiant","year":"1979","unstructured":"Valiant L (1979) The complexity of enumeration and reliability problems. SIAM J Comput 8:410\u2013421","journal-title":"SIAM J Comput"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_747","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:48:40Z","timestamp":1792108120000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_747"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_747","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}