{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T05:02:56Z","timestamp":1787893376891,"version":"build-2784847793"},"reference-count":38,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1989,7,1]],"date-time":"1989-07-01T00:00:00Z","timestamp":615254400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8782,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1989,7]]},"DOI":"10.1016\/0890-5401(89)90067-9","type":"journal-article","created":{"date-parts":[[2004,12,1]],"date-time":"2004-12-01T19:24:20Z","timestamp":1101929060000},"page":"93-133","source":"Crossref","is-referenced-by-count":414,"title":["Approximate counting, uniform generation and rapidly mixing Markov chains"],"prefix":"10.1016","volume":"82","author":[{"given":"Alistair","family":"Sinclair","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/0890-5401(89)90067-9_BIB1","series-title":"S\u00e9minaire de Probabilit\u00e9s XVII","first-page":"243","article-title":"Random walks on finite groups and rapidly mixing Markov chains","volume":"Vol. 986","author":"Aldous","year":"1981"},{"key":"10.1016\/0890-5401(89)90067-9_BIB2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1017\/S0269964800000267","article-title":"On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing","volume":"1","author":"Aldous","year":"1987","journal-title":"Prob. Engrg. Inform. Sci."},{"key":"10.1016\/0890-5401(89)90067-9_BIB3","doi-asserted-by":"crossref","first-page":"333","DOI":"10.2307\/2323590","article-title":"Shuffling cards and stopping times","volume":"93","author":"Aldous","year":"1986","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/0890-5401(89)90067-9_BIB4","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0196-8858(87)90006-6","article-title":"Strong uniform times and finite random walks","volume":"8","author":"Aldous","year":"1987","journal-title":"Adv. in Appl. Math."},{"key":"10.1016\/0890-5401(89)90067-9_BIB5","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","article-title":"Eigenvalues and expanders","volume":"6","author":"Alon","year":"1986","journal-title":"Combinatorica"},{"key":"10.1016\/0890-5401(89)90067-9_BIB6","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","article-title":"\u03bb1, isoperimetric inequalities for graphs and superconcentrators","volume":"38","author":"Alon","year":"1985","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/0890-5401(89)90067-9_BIB7","series-title":"Proceedings 15th ACM Symposium on Theory of Computing","first-page":"184","article-title":"How to generate random integers with known factorisation","author":"Bach","year":"1983"},{"key":"10.1016\/0890-5401(89)90067-9_BIB8","first-page":"1","article-title":"Monte Carlo investigations of phase transitions and critical phenomena","volume":"Vol. 5b","author":"Binder","year":"1976"},{"key":"10.1016\/0890-5401(89)90067-9_BIB9","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","article-title":"A probabilistic proof of an asymptotic formula for the number of labelled regular graphs","volume":"1","author":"Bollob\u00e1s","year":"1980","journal-title":"European J. Combin."},{"key":"10.1016\/0890-5401(89)90067-9_BIB10","author":"Bollob\u00e1s","year":"1985"},{"key":"10.1016\/0890-5401(89)90067-9_BIB11","series-title":"Proceedings, 18th ACM Symposium on Theory of Computing","first-page":"50","article-title":"How hard is it to marry at random? (On the approximation of the permanent)","author":"Broder","year":"1986"},{"key":"10.1016\/0890-5401(89)90067-9_BIB12","author":"Cai","year":"1986"},{"key":"10.1016\/0890-5401(89)90067-9_BIB13","series-title":"Problems in Analysis","first-page":"195","article-title":"A lower bound for the smallest eigenvalue of the Laplacian","author":"Cheeger","year":"1970"},{"key":"10.1016\/0890-5401(89)90067-9_BIB14","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1090\/S0002-9947-1984-0743744-X","article-title":"Difference equations, isoperimetric inequality and transience of certain random walks","volume":"284","author":"Dodziuk","year":"1984","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0890-5401(89)90067-9_BIB15","volume":"Vol. I","author":"Feller","year":"1968"},{"key":"10.1016\/0890-5401(89)90067-9_BIB16","author":"Garey","year":"1979"},{"key":"10.1016\/0890-5401(89)90067-9_BIB17","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","article-title":"Computational complexity of probabilistic Turing machines","volume":"6","author":"Gill","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(89)90067-9_BIB18","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0196-6774(83)90022-6","article-title":"Random spanning tree","volume":"4","author":"Gu\u00e9noche","year":"1983","journal-title":"J. Algorithms"},{"key":"10.1016\/0890-5401(89)90067-9_BIB19","series-title":"Proceedings, 20th ACM Symposium on Theory of Computing","first-page":"235","article-title":"Conductance and the rapid mixing property for Markov chains: The approximation of the permanent resolved","author":"Jerrum","year":"1988"},{"key":"10.1016\/0890-5401(89)90067-9_BIB20","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","article-title":"Random generation of combinatorial structures from a uniform distribution","volume":"43","author":"Jerrum","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(89)90067-9_BIB21","series-title":"Proceedings, 24th IEEE Symposium on Foundations of Computer Science","first-page":"56","article-title":"Monte-Carlo algorithms for enumeration and reliability problems","author":"Karp","year":"1983"},{"key":"10.1016\/0890-5401(89)90067-9_BIB22","author":"Keilson","year":"1979"},{"key":"10.1016\/0890-5401(89)90067-9_BIB23","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimisation by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"10.1016\/0890-5401(89)90067-9_BIB24","author":"Kolmogorov","year":"1970"},{"key":"10.1016\/0890-5401(89)90067-9_BIB25","first-page":"557","article-title":"Bounds on the L2 spectrum for Markov chains and Markov processes: A generalization of Cheeger's inequality","volume":"309","author":"Lawler","year":"1988","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0890-5401(89)90067-9_BIB26","first-page":"15","article-title":"Asymptotics for symmetric 0\u20131 matrices with prescribed row sums","volume":"19A","author":"McKay","year":"1985","journal-title":"Ars Combin."},{"key":"10.1016\/0890-5401(89)90067-9_BIB27","author":"Nijenhuis","year":"1978"},{"key":"10.1016\/0890-5401(89)90067-9_BIB28","series-title":"Proceedings, 3rd International Colloquium on Automata, Languages and Programming","first-page":"322","article-title":"Optimal algorithms for self-reducible problems","author":"Schnorr","year":"1976"},{"key":"10.1016\/0890-5401(89)90067-9_BIB29","author":"Seneta","year":"1981"},{"key":"10.1016\/0890-5401(89)90067-9_BIB30","article-title":"Randomised Algorithms for Counting and Generating Combinatorial Structures","author":"Sinclair","year":"1988"},{"key":"10.1016\/0890-5401(89)90067-9_BIB31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1977","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(89)90067-9_BIB32","series-title":"Proceedings, 15th ACM Symposium on Theory of Computing","first-page":"118","article-title":"The complexity of approximate counting","author":"Stockmeyer","year":"1983"},{"key":"10.1016\/0890-5401(89)90067-9_BIB33","first-page":"265","article-title":"On the generation of random graphs with given properties and known distribution","volume":"13","author":"Tinhofer","year":"1979","journal-title":"Appl. Comput. Sci., Ber. Prakt. Inf."},{"key":"10.1016\/0890-5401(89)90067-9_BIB34","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The complexity of computing the permanent","volume":"8","author":"Valiant","year":"1979","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(89)90067-9_BIB35","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","article-title":"The complexity of enumeration and reliability problems","volume":"8","author":"Valiant","year":"1979","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(89)90067-9_BIB36","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0196-6774(81)90021-3","article-title":"The uniform selection of free trees","volume":"2","author":"Wilf","year":"1981","journal-title":"J. Algorithms"},{"key":"10.1016\/0890-5401(89)90067-9_BIB37","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0196-6774(84)90030-0","article-title":"Generating random regular graphs","volume":"5","author":"Wormald","year":"1984","journal-title":"J. Algorithms"},{"key":"10.1016\/0890-5401(89)90067-9_BIB38","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1137\/0216048","article-title":"Generating random unlabelled graphs","volume":"16","author":"Wormald","year":"1987","journal-title":"SIAM J. Comput."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540189900679?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540189900679?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,1]],"date-time":"2019-02-01T13:26:55Z","timestamp":1549027615000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0890540189900679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,7]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1989,7]]}},"alternative-id":["0890540189900679"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(89)90067-9","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1989,7]]}}}