{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T22:54:36Z","timestamp":1743116076313,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"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_43","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"529-541","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximately Counting H-Colourings is $$\\#\\mathrm {BIS}$$-Hard"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Galanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"3","key":"43_CR1","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00453-003-1073-y","volume":"38","author":"ME Dyer","year":"2003","unstructured":"Dyer, M.E., Goldberg, L.A., Greenhill, C.S., Jerrum, M.: The relative complexity of approximate counting problems. Algorithmica 38(3), 471\u2013500 (2003)","journal-title":"Algorithmica"},{"issue":"1","key":"43_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2003.09.001","volume":"189","author":"ME Dyer","year":"2004","unstructured":"Dyer, M.E., Goldberg, L.A., Jerrum, M.: Counting and sampling $$H$$-colourings. Information and Computation 189(1), 1\u201316 (2004)","journal-title":"Information and Computation"},{"issue":"3\u20134","key":"43_CR3","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":"ME Dyer","year":"2000","unstructured":"Dyer, M.E., Greenhill, C.: The complexity of counting graph homomorphisms. Random Structures and Algorithms 17(3\u20134), 260\u2013289 (2000)","journal-title":"Random Structures and Algorithms"},{"key":"43_CR4","unstructured":"Ge, Q., \u0160tefankovi\u010d, D.: A graph polynomial for independent sets of bipartite graphs. In: FSTTCS, pp. 240\u2013250 (2010)"},{"issue":"5","key":"43_CR5","first-page":"1","volume":"17","author":"L Goldberg","year":"2012","unstructured":"Goldberg, L., Jerrum, M.: A counterexample to rapid mixing of the Ge-\u0160tefankovi\u010d process. Electron. Commun. Probab. 17(5), 1\u20136 (2012)","journal-title":"Electron. Commun. Probab."},{"issue":"2","key":"43_CR6","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/S0097539702408363","volume":"33","author":"LA Goldberg","year":"2004","unstructured":"Goldberg, L.A., Kelk, S., Paterson, M.: The complexity of choosing an $$H$$-coloring (Nearly) uniformly at random. SIAM J. Comput. 33(2), 416\u2013432 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"43_CR7","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":"43_CR8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"MR Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. TCS 43, 169\u2013188 (1986)","journal-title":"TCS"},{"key":"43_CR9","unstructured":"Kelk, S.: On the relative complexity of approximately counting H-colourings. Ph.D. Thesis, University of Warwick (2004)"},{"key":"43_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02280291","volume":"18","author":"L Lov\u00e1sz","year":"1967","unstructured":"Lov\u00e1sz, L.: Operations with structures. Acta Math. Acad. Sci. Hungar. 18, 321\u2013328 (1967)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"43_CR11","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s00440-007-0131-9","volume":"143","author":"E Mossel","year":"2009","unstructured":"Mossel, E., Weitz, D., Wormald, N.: On the hardness of sampling independent sets beyond the tree threshold. Prob. Theory Related. Fields 143, 401\u2013439 (2009)","journal-title":"Prob. Theory Related. Fields"}],"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_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T16:20:39Z","timestamp":1674836439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}