{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:11Z","timestamp":1794381071815,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_27","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"294-306","source":"Crossref","is-referenced-by-count":14,"title":["The Complexity of Partition Functions"],"prefix":"10.1007","author":[{"given":"Andrei","family":"Bulatov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. In: Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, FOCS 2003, pp. 562\u2013571 (2003)","DOI":"10.1109\/SFCS.2003.1238229"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, FOCS 2002, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. In: Proceedings of the 18th Annual IEEE Simposium on Logic in Computer Science, pp. 321\u2013330 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., Grohe, M.: The complexity of partition functions. Technical Report PRG-RR-04-04, Computing Laboratory, University of Oxford, Oxford, UK (2004)","DOI":"10.1007\/978-3-540-27836-8_27"},{"issue":"1","key":"27_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Information and Computation\u00a0125(1), 1\u201312 (1996)","journal-title":"Information and Computation"},{"key":"27_CR6","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.: The complexity of counting graph homomorphisms. Random Structures and Algorithms\u00a017, 260\u2013289 (2000)","journal-title":"Random Structures and Algorithms"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/3-540-45726-7_5","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M.E. Dyer","year":"2002","unstructured":"Dyer, M.E., Goldberg, L.A., Jerrum, M.: Counting and sampling H-colourings. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 51\u201367. Springer, Heidelberg (2002)"},{"key":"27_CR8","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 Journal of Computing\u00a028, 57\u2013104 (1998)","journal-title":"SIAM Journal of Computing"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1002\/rsa.10090","volume":"23","author":"L.A. Goldberg","year":"2003","unstructured":"Goldberg, L.A., Jerrum, M., Paterson, M.: The computational complexity of two-state spin systems. Random Structures and Algorithms\u00a023, 133\u2013154 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Goldberg, L.A., Kelk, S., Paterson, M.: The complexity of choosing an Hcolouring (nearly) uniformly at random. In: Proceedings of the 34rd ACM Simposium on Theory of Computing, pp. 53\u201362 (2002)","DOI":"10.1145\/509914.509917"},{"key":"27_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimazation","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimazation, 2nd edn. Springer, Heidelberg (1993)","edition":"2"},{"key":"27_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, Ser. B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Ser. B"},{"issue":"4","key":"27_CR13","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1090\/S0002-9947-96-01537-1","volume":"348","author":"P. Hell","year":"1996","unstructured":"Hell, P., Ne\u0161et\u0159il, J., Zhu, X.: Duality and polynomial testing of tree homomorphisms. Trans. of the AMS\u00a0348(4), 1281\u20131297 (1996)","journal-title":"Trans. of the AMS"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F. Jaeger","year":"1990","unstructured":"Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society\u00a0108, 35\u201353 (1990)","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"issue":"4","key":"27_CR15","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P.G. Jeavons","year":"1997","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"27_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Complexity Theory of Real Functions","author":"K. Ko","year":"1991","unstructured":"Ko, K.: Complexity Theory of Real Functions. Birkh\u00e4user, Basel (1991)"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:23:53Z","timestamp":1605741833000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_27","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b99859","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}