{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:56Z","timestamp":1759063616147},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441472"},{"type":"electronic","value":"9783540457268"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45726-7_5","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T05:55:49Z","timestamp":1186811749000},"page":"51-67","source":"Crossref","is-referenced-by-count":3,"title":["Counting and Sampling H-Colourings"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie A.","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":[[2002,8,23]]},"reference":[{"key":"5_CR1","unstructured":"G.R. Brightwell and L.A. Goldberg, personal communication."},{"issue":"1","key":"5_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1006\/jctb.1999.1935","volume":"78","author":"G.R. Brightwell","year":"2000","unstructured":"G.R. Brightwell and P. Winkler, Gibbs measures and dismantlable graphs, J. Com-bin. Theory Ser. B 78(1) 141\u2013166 (2000)","journal-title":"J. Com-bin. Theory Ser. B"},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1006\/jagm.2000.1142","volume":"39","author":"C. Cooper","year":"2001","unstructured":"C. Cooper, M. Dyer and A. Frieze, On Markov chains for randomly H-colouring a graph, Journal of Algorithms, 39(1) (2001) 117\u2013134.","journal-title":"Journal of Algorithms"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"M. Dyer and C. Greenhill, Random walks on combinatorial objects. In J.D. Lamb and D.A. Preece, editors, Surveys in Combinatorics, volume 267 of London Mathematical Society Lecture Note Series, pages 101\u2013136. Cambridge University Press, 1999.","DOI":"10.1017\/CBO9780511721335.005"},{"key":"5_CR5","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":"M. Dyer and C. Greenhill, The complexity of counting graph homomorphisms. Random Structures and Algorithms, 17 (2000) 260\u2013289.","journal-title":"Random Structures and Algorithms"},{"key":"5_CR6","unstructured":"M. Dyer, M. Jerrum and E. Vigoda, Rapidly mixing Markov chains for disman-tleable constraint graphs. In J. Nesetril and P. Winkler, editors, Proceedings of a DIM ACS\/DIMATI A Workshop on Graphs, Morphisms and Statistical Physics, March 2001, to appear."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"L.A. Goldberg, Computation in permutation groups: counting and randomly sampling orbits. In J.W.P. Hirschfeld, editor, Surveys in Combinatorics, volume 288 of London Mathematical Society Lecture Note Series, pages 109\u2013143. Cambridge University press, 2001.","DOI":"10.1017\/CBO9780511721328.007"},{"key":"5_CR8","unstructured":"L.A. Goldberg, M. Jerrum and M. Paterson, The computational complexity of two-state spin systems, Pre-print (2001)."},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"L.A. Goldberg, S. Kelk and M. Paterson, The complexity of choosing an H- colouring (nearly) uniformly at random, To appear in STOC 2002.","DOI":"10.1145\/509907.509917"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"O. Goldreich, The Foundations of Cryptography-Volume 1, (Cambridge University Press, 2001)","DOI":"10.1017\/CBO9780511546891"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/rsa.3240070205","volume":"7","author":"M. Jerrum","year":"1995","unstructured":"M. Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures and Algorithms, 7 (1995) 157\u2013165.","journal-title":"Random Structures and Algorithms"},{"key":"5_CR12","unstructured":"M. Jerrum, Sampling and Counting. Chapter 3 of Counting, Sampling and Integrating: Algorithms and Complexity, Birkh\u00e4user, Basel. (In preparation.)"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"M.R. Jerrum, L.G. Valiant, and V.V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoretical Computer Science, 43 (1986) 169\u2013188.","journal-title":"Theoretical Computer Science"},{"key":"5_CR14","unstructured":"C.H. Papadimitriou, Computational Complexity, (Addison-Wesley, 1994)"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45726-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T19:04:30Z","timestamp":1556737470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45726-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441472","9783540457268"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45726-7_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}