{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:59:49Z","timestamp":1725663589996},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540194224"},{"type":"electronic","value":"9783540392644"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19422-3_11","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:09:26Z","timestamp":1330200566000},"page":"134-148","source":"Crossref","is-referenced-by-count":3,"title":["Approximate counting, uniform generation and rapidly mixing markov chains extended abstract"],"prefix":"10.1007","author":[{"given":"Alistair","family":"Sinclair","sequence":"first","affiliation":[]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Aldous, D. Random walks on finite groups and rapidly mixing Markov chains. S\u00e9minaire de Probabilit\u00e9s XVII, 1981\/82, Springer Lecture Notes in Mathematics 986, pp. 243\u2013297","DOI":"10.1007\/BFb0068322"},{"key":"11_CR2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1080\/00029890.1986.11971821","volume":"93","author":"D. Aldous","year":"1986","unstructured":"Aldous, D. and Diaconis, P. Shuffling cards and stopping times. American Mathematical Monthly 93 (1986), pp. 333\u2013348","journal-title":"American Mathematical Monthly"},{"issue":"2","key":"11_CR3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"Alon, N. Eigenvalues and expanders. Combinatorica 6 (2) (1986), pp. 83\u201396","journal-title":"Combinatorica"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N. Alon","year":"1985","unstructured":"Alon, N. and Milman, V.D. \u03bb1, isoperimetric inequalities for graphs and superconcentrators. Journal of Combinatorial Theory Series B 38 (1985), pp. 73\u201388","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"11_CR5","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"Bollob\u00e1s, B., Random Graphs (Academic Press, London, 1985)"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Broder, A.Z. How hard is it to marry at random? (On the approximation of the permanent). Proc. 18th ACM Symposium on Theory of Computing, 1986, pp. 50\u201358","DOI":"10.1145\/12130.12136"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Cheeger, J. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analysis (R. C. Gunning ed.) Princeton University Press, 1970, pp. 195\u2013199","DOI":"10.1515\/9781400869312-013"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0196-6774(83)90021-4","volume":"4","author":"J.D. Dixon","year":"1983","unstructured":"Dixon, J.D. and Wilf, H.S. The random selection of unlabelled graphs. Journal of Algorithms 4 (1983), pp. 205\u2013213","journal-title":"Journal of Algorithms"},{"key":"11_CR9","volume-title":"An introduction to probability theory and its applications, Volume I","author":"W. Feller","year":"1968","unstructured":"Feller, W. An introduction to probability theory and its applications, Volume I (3rd ed.) (John Wiley, New York, 1968)","edition":"3rd ed."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G. and Vazirani, V.V. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43 (1986), pp. 169\u2013188","journal-title":"Theoretical Computer Science"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Jerrum, M.R. and Sinclair, A.J. Conductance and the rapid mixing property for Markov chains. Proc. 20th ACM Symposium on Theory of Computing (1988), to appear","DOI":"10.1145\/62212.62234"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.M. and Luby, M. Monte-Carlo algorithms for enumeration and reliability problems. Proc. 24th IEEE Symposium on Foundations of Computer Science, 1983, pp. 56\u201364","DOI":"10.1109\/SFCS.1983.35"},{"key":"11_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6200-8","volume-title":"Markov chain models \u2014 rarity and exponentiality","author":"J. Keilson","year":"1979","unstructured":"Keilson, J. Markov chain models \u2014 rarity and exponentiality (Springer-Verlag, New York, 1979)"},{"key":"11_CR14","first-page":"15","volume":"19A","author":"B.D. McKay","year":"1985","unstructured":"McKay, B.D. Asymptotics for symmetric 0\u20131 matrices with prescribed row sums. Ars Combinatoria 19A (1985), pp. 15\u201325","journal-title":"Ars Combinatoria"},{"key":"11_CR15","volume-title":"Combinatorial Algorithms","author":"A. Nijenhuis","year":"1978","unstructured":"Nijenhuis, A. and Wilf, H.S. Combinatorial Algorithms (2nd ed.) (Academic Press, Orlando, 1978)","edition":"2nd ed."},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P. Optimal algorithms for self-reducible problems. Proc. 3rd International Colloquium on Automata, Languages and Programming, 1976, pp. 322\u2013337","DOI":"10.1016\/0304-3975(76)90070-0"},{"key":"11_CR17","unstructured":"Sinclair, A.J. PhD Thesis, University of Edinburgh (in preparation)"},{"key":"11_CR18","unstructured":"Sinclair, A.J. and Jerrum, M.R. Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains Internal Report CSR-241-87, Dept. of Computer Science, University of Edinburgh (submitted to Information and Computation)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L. The complexity of approximate counting. Proc. 15th ACM Symposium on Theory of Computing, 1983, pp. 118\u2013126","DOI":"10.1145\/800061.808740"},{"key":"11_CR20","first-page":"265","volume":"13","author":"G. Tinhofer","year":"1979","unstructured":"Tinhofer, G. On the generation of random graphs with given properties and known distribution. Appl. Comput. Sci. 13 (1979), pp. 265\u2013297","journal-title":"Appl. Comput. Sci."},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G. The complexity of computing the permanent. Theoretical Computer Science 8 (1979), pp. 189\u2013201","journal-title":"Theoretical Computer Science"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0196-6774(81)90021-3","volume":"2","author":"H.S. Wilf","year":"1981","unstructured":"Wilf, H.S. The uniform selection of free trees. Journal of Algorithms 2 (1981), pp. 204\u2013207","journal-title":"Journal of Algorithms"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0196-6774(84)90030-0","volume":"5","author":"N.C. Wormald","year":"1984","unstructured":"Wormald, N.C. Generating random regular graphs. Journal of Algorithms 5 (1984), pp. 247\u2013280","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19422-3_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T02:29:48Z","timestamp":1640917788000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19422-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194224","9783540392644"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-19422-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}