{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T13:52:49Z","timestamp":1773755569403,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,7,21]],"date-time":"2009-07-21T00:00:00Z","timestamp":1248134400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,12]]},"DOI":"10.1007\/s00453-009-9340-1","type":"journal-article","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T18:20:47Z","timestamp":1248114047000},"page":"860-910","source":"Crossref","is-referenced-by-count":78,"title":["A Sequential Algorithm for Generating Random Graphs"],"prefix":"10.1007","volume":"58","author":[{"given":"Mohsen","family":"Bayati","sequence":"first","affiliation":[]},{"given":"Jeong Han","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Amin","family":"Saberi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,7,21]]},"reference":[{"key":"9340_CR1","doi-asserted-by":"crossref","unstructured":"Alderson, D., Doyle, J., Willinger, W.: Toward and optimization-driven framework for designing and generating realistic Internet topologies. HotNets (2002)","DOI":"10.1145\/774763.774769"},{"key":"9340_CR2","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (1992)"},{"key":"9340_CR3","doi-asserted-by":"crossref","unstructured":"Amraoui, A., Montanari, A., Urbanke, R.: How to find good finite-length codes: from art towards science. Preprint, cs.IT\/0607064 (2006)","DOI":"10.1002\/ett.1182"},{"key":"9340_CR4","doi-asserted-by":"crossref","unstructured":"Bassetti, F., Diaconis, P.: Examples comparing importance sampling and the Metropolis algorithm (2005)","DOI":"10.1215\/ijm\/1258059470"},{"key":"9340_CR5","doi-asserted-by":"crossref","unstructured":"Bayati, M., Montanari, A., Saberi, A.: Generating random graphs with large girth. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2009)","DOI":"10.1137\/1.9781611973068.63"},{"issue":"3","key":"9340_CR6","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0097-3165(78)90059-6","volume":"24","author":"E.A. Bender","year":"1978","unstructured":"Bender, E.A., Canfield, E.R.: The asymptotic number of labeled graphs with given degree sequence. J.\u00a0Comb. Theory Ser. A 24(3), 296\u2013307 (1978)","journal-title":"J.\u00a0Comb. Theory Ser. A"},{"key":"9340_CR7","doi-asserted-by":"crossref","unstructured":"Bez\u00e1kov\u00e1, I., Bhatnagar, N., Vigoda, E.: Sampling binary contingency tables with a greedy start. In: Symposium on Discrete Algorithms (SODA) (2006)","DOI":"10.1145\/1109557.1109604"},{"key":"9340_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/11841036_15","volume-title":"Proceedings of Annual European Symposium, vol. 14","author":"I. Bez\u00e1kov\u00e1","year":"2006","unstructured":"Bez\u00e1kov\u00e1, I., Sinclair, A., S\u0306tefankovi\u010d, D., Vigoda, E.: Negative examples for sequential importance sampling of binary contingency tables. In: Proceedings of Annual European Symposium, vol. 14. Lecture Notes in Computer Science, vol. 4168, pp.\u00a0136\u2013147. Springer, Berlin (2006)"},{"issue":"3","key":"9340_CR9","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1214\/08-AAP558","volume":"19","author":"J. Blanchet","year":"2009","unstructured":"Blanchet, J.: Efficient importance sampling for binary contingency tables. Ann. Appl. Probab. 19(3), 949\u2013982 (2009)","journal-title":"Ann. Appl. Probab."},{"key":"9340_CR10","unstructured":"Blitzstein, J., Diaconis, P.: A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Ann. Appl. Probab. (2005, submitted)"},{"issue":"4","key":"9340_CR11","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","volume":"1","author":"B. Bollob\u00e1s","year":"1980","unstructured":"Bollob\u00e1s, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J.\u00a0Comb. 1(4), 311\u2013316 (1980)","journal-title":"Eur. J.\u00a0Comb."},{"key":"9340_CR12","unstructured":"Bu, T., Towsley, D.: On distinguishing between Internet power law topology generator. In: INFOCOM (2002)"},{"key":"9340_CR13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1198\/016214504000001303","volume":"100","author":"Y. Chen","year":"2005","unstructured":"Chen, Y., Diaconis, P., Holmes, S., Liu, J.S.: Sequential Monte Carlo methods for statistical analysis of tables. J.\u00a0Am. Stat. Assoc. 100, 109\u2013120 (2005)","journal-title":"J.\u00a0Am. Stat. Assoc."},{"issue":"2","key":"9340_CR14","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/PL00012580","volume":"6","author":"F. Chung","year":"2002","unstructured":"Chung, F., Lu, L.: Connected components in random graphs with given expected degree sequence. Ann. Comb. 6(2), 125\u2013145 (2002)","journal-title":"Ann. Comb."},{"key":"9340_CR15","doi-asserted-by":"crossref","unstructured":"Cooper, C., Dyer, M., Greenhill, C.: Sampling regular graphs and peer-to-peer network. Comb. Probab. Comput. 16 (2007)","DOI":"10.1017\/S0963548306007978"},{"key":"9340_CR16","series-title":"IMA Volumes in Mathematics and Its Applications","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-1-4612-0801-3_3","volume-title":"Discrete Probability and Algorithms","author":"P. Diaconis","year":"1995","unstructured":"Diaconis, P., Gangolli, A.: Rectangular arrays with fixed margins. In: Discrete Probability and Algorithms, Minneapolis, MN, 1993. IMA Volumes in Mathematics and Its Applications, vol. 72, pp. 15\u201341. Springer, New York (1995)"},{"key":"9340_CR17","doi-asserted-by":"crossref","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the Internet topology. In: SIGCOM (1999)","DOI":"10.1145\/316188.316229"},{"key":"9340_CR18","unstructured":"Gkantsidis, C., Mihail, M., Zegura, E.: The Markov chain simulation method for generating connected power law random graphs. Alenex (2003)"},{"issue":"1","key":"9340_CR19","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"M. Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82(1), 93\u2013133 (1989)","journal-title":"Inf. Comput."},{"issue":"1","key":"9340_CR20","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0304-3975(90)90164-D","volume":"73","author":"M. Jerrum","year":"1990","unstructured":"Jerrum, M., Sinclair, A.: Fast uniform generation of regular graphs. Theor. Comput. Sci. 73(1), 91\u2013100 (1990)","journal-title":"Theor. Comput. Sci."},{"key":"9340_CR21","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. Jerrum","year":"1986","unstructured":"Jerrum, M., Valiant, L., Vazirani, V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, 169\u2013188 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"9340_CR22","first-page":"101","volume-title":"Random Graphs","author":"M. Jerrum","year":"1992","unstructured":"Jerrum, M., Sinclair, A., McKay, B.: When is a graphical sequence stable? In: Random Graphs, Pozna\u0144, 1989, vol. 2, pp. 101\u2013115. Wiley-Interscience, New York (1992)"},{"key":"9340_CR23","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1002\/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO;2-G","volume":"14","author":"R. Kannan","year":"1999","unstructured":"Kannan, R., Tetali, P., Vempala, S.: Simple Markov chain algorithms for generating bipartite graphs and tournaments. Random Struct. Algorithms 14, 293\u2013308 (1999)","journal-title":"Random Struct. Algorithms"},{"key":"9340_CR24","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1017\/S0963548300001528","volume":"4","author":"J.H. Kim","year":"1995","unstructured":"Kim, J.H.: On Brooks\u2019 theorem for sparse graphs. Comb. Probab. Comput. 4, 97\u2013132 (1995)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"9340_CR25","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s004930070014","volume":"20","author":"J.H. Kim","year":"2000","unstructured":"Kim, J.H., Vu, V.H.: Concentration of multivariate polynomials and its applications. Combinatorica 20(3), 417\u2013434 (2000)","journal-title":"Combinatorica"},{"key":"9340_CR26","doi-asserted-by":"crossref","unstructured":"Kim, J.H., Vu, V.H.: Generating random regular graphs. In: STOC 2003, pp. 213\u2013222","DOI":"10.1145\/780542.780576"},{"key":"9340_CR27","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/j.aim.2003.10.007","volume":"188","author":"J.H. Kim","year":"2004","unstructured":"Kim, J.H., Vu, V.: Sandwiching random graphs. Adv. Math. 188, 444\u2013469 (2004)","journal-title":"Adv. Math."},{"issue":"4271","key":"9340_CR28","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1126\/science.194.4271.1235","volume":"194","author":"D. Knuth","year":"1976","unstructured":"Knuth, D.: Mathematics and computer science: coping with finiteness. Science 194(4271), 1235\u20131242 (1976)","journal-title":"Science"},{"key":"9340_CR29","first-page":"15","volume":"19","author":"B. McKay","year":"1985","unstructured":"McKay, B.: Asymptotics for symmetric 0-1 matrices with prescribed row sums. Ars Combinatoria A 19, 15\u201325 (1985)","journal-title":"Ars Combinatoria A"},{"issue":"1","key":"9340_CR30","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/0196-6774(90)90029-E","volume":"11","author":"B. McKay","year":"1990","unstructured":"McKay, B., Wormald, N.C.: Uniform generation of random regular graphs of moderate degree. J.\u00a0Algorithms 11(1), 52\u201367 (1990)","journal-title":"J.\u00a0Algorithms"},{"issue":"4","key":"9340_CR31","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF01275671","volume":"11","author":"B. McKay","year":"1991","unstructured":"McKay, B., Wormald, N.C.: Asymptotic enumeration by degree sequence of graphs with degrees o(n 1\/2). Combinatorica 11(4), 369\u2013382 (1991)","journal-title":"Combinatorica"},{"issue":"2","key":"9340_CR32","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/505680.505683","volume":"30","author":"A. Medina","year":"2000","unstructured":"Medina, A., Matta, I., Byers, J.: On the origin of power laws in Internet topologies. ACM Comput. Commun. Rev. 30(2), 18\u201328 (2000)","journal-title":"ACM Comput. Commun. Rev."},{"key":"9340_CR33","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R. Milo","year":"2002","unstructured":"Milo, R., ShenOrr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298, 824\u2013827 (2002)","journal-title":"Science"},{"key":"9340_CR34","unstructured":"Milo, R., Kashtan, N., Itzkovitz, S., Newman, M., Alon, U.: On the uniform generation of random graphs with prescribed degree sequences. http:\/\/arxiv.org\/PS_cache\/cond-mat\/pdf\/0312\/0312028.pdf (2004)"},{"issue":"2\u20133","key":"9340_CR35","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/rsa.3240060204","volume":"6","author":"M. Molloy","year":"1995","unstructured":"Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2\u20133), 161\u2013179 (1995)","journal-title":"Random Struct. Algorithms"},{"key":"9340_CR36","doi-asserted-by":"crossref","unstructured":"Sinclair, A.: Personal communication (2006)","DOI":"10.12968\/sece.2006.11.761"},{"issue":"4","key":"9340_CR37","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1017\/S0963548399003867","volume":"8","author":"A. Steger","year":"1997","unstructured":"Steger, A., Wormald, N.C.: Generating random regular graphs quickly. Comb. Probab. Comput. 8(4), 377\u2013396 (1997) (English summary in Random Graphs and Combinatorial Structures, Oberwolfach)","journal-title":"Comb. Probab. Comput."},{"key":"9340_CR38","doi-asserted-by":"crossref","unstructured":"Tangmunarunkit, H., Govindan, R., Jamin, S., Shenker, S., Willinger, W.: Network topology generators: degree based vs. structural. In: ACM SIGCOM (2002)","DOI":"10.1145\/633025.633040"},{"issue":"3","key":"9340_CR39","first-page":"267","volume":"20","author":"V.H. Vu","year":"2002","unstructured":"Vu, V.H.: Concentration of non-Lipschitz functions and applications, Probabilistic methods in combinatorial optimization. Random Struct. Algorithms 20(3), 267\u2013316 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"9340_CR40","series-title":"London Mathematical Society Lecture Note Series","first-page":"239","volume-title":"Surveys in Combinatorics. Canterbury","author":"N.C. Wormald","year":"1999","unstructured":"Wormald, N.C.: Models of random regular graphs. In: Surveys in Combinatorics. Canterbury. London Mathematical Society Lecture Note Series, vol. 265, pp. 239\u2013298. Cambridge University Press, Cambridge (1999)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9340-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9340-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9340-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T05:32:48Z","timestamp":1739251968000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9340-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,21]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["9340"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9340-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,21]]}}}