Rejection sampling of bipartite graphs with given degree sequence

[1] M. Bayati, J. H. Kim and A. Saberi, A sequential algorithm for generating random graphs, Algorithmica, 58 (2010), 860–910.10.1007/s00453-009-9340-1Search in Google Scholar

[2] E. A. Bender and E. R. Canfield, The assymptotic number of labelled graphs with given degree sequence, J. Combin. Theory, Ser A., 24 (3) (1978), 296–307.10.1016/0097-3165(78)90059-6Search in Google Scholar

[3] J. Blitzstein and P. Diaconis, A sequential importance sampling algorithm for generating random graphs with prescribed degree sequence, Internet Math., 6 (4) (2011), 489–522.10.1080/15427951.2010.557277Search in Google Scholar

[4] F. Boesch and F. Harary, Line removal algorithms for graphs and their degree lists, IEEE Trans. Circuits Syst. CAS, 23 (12) (1976), 778–782.10.1109/TCS.1976.1084170Search in Google Scholar

[5] B. Bollobas, A probalistic proof of an assymptotic formula for the number of labelled regular graphs, European J. Combin., 1 (4) (1980), 311–316.10.1016/S0195-6698(80)80030-8Search in Google Scholar

[6] R. A. Brualdi, Matrices of zeroes and ones with fixed row and column sum vectors, Linear Algebra Appl., 33 (1980), 159–23110.1016/0024-3795(80)90105-6Search in Google Scholar

[7] T. Brylawsky and J. Oxley, The Tutte polynomial and its applications, in N. White, ed., Matroid Applications, Encyclopedia of Mathematics and its Applications, Cambridge University Press, (1992) 123–225.10.1017/CBO9780511662041.007Search in Google Scholar

[8] Y. Chen, P. Diaconis, S. Holmes and J. S. Liu, Sequential Monte Carlo methods for statistical analysis of tables, J. Amer. Stat. Assoc., 100 (2005), 109–120.10.1198/016214504000001303Search in Google Scholar

[9] G. W. Cobb and Y. Chen, An application of Markov Chains Monte Carlo to community ecology, American Math. Monthly, 110 (2003), 265–288.10.1080/00029890.2003.11919964Search in Google Scholar

[10] C. Cooper, M. Dyer and C. Greenhill, Sampling regular graphs and Peer-to-Peer network, Combinatorics, Probability and Computing, 16 (2007), 557–594.10.1017/S0963548306007978Search in Google Scholar

[11] P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins. In Discrete Probability and Algorithms (Minneapolis, MN, 1993), IMA Vol. Math. Appl. 72, 15–41, New York Springer, 1995.10.1007/978-1-4612-0801-3_3Search in Google Scholar

[12] P. Diaconnis and B. Sturmfels, Algebraic Algorithms for sampling from conditional distributions, Annal. Statist., 26 (11) (1998), 363–3977.10.1214/aos/1030563990Search in Google Scholar

[13] P. Erdős and T. G. Gallai, Graphs with prescribed degrees of vertices (Hungarian), Mat. Lapok, 11 (1960), 264–274.Search in Google Scholar

[14] P. L. Erdős, I. Miklós and Z. Toroczkai, A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs, Electron. J. Combin., 17(1) (2010), #R66.10.37236/338Search in Google Scholar

[15] M. Gail and N. Mantel, Counting the number of r x c contingency tables with fixed margins, J. American Stat. Assoc., 72 (1977), 859–862.10.1080/01621459.1977.10479971Search in Google Scholar

[16] G. Guenoche, Counting and selecting at random bipartite graphs with fixed degrees, Revue francaise d’automatique, d’informatique et de recherche operationelle, 24 (1) (1990), 1–14.10.1051/ro/1990240100011Search in Google Scholar

[17] J. Guillaume and M. Latapy, Bipartite Graphs as models of complex networks, Preprint.Search in Google Scholar

[18] M. Jerrum and A. Sinclair, Approximating the permanent, SIAM J. Com-put., 18 (6) (1989) 1149–1178.10.1137/0218077Search in Google Scholar

[19] M. Jerrum and A. Sinclair, Fast uniform generation of regular graphs, Theoretical Computer Science, 73 (1) (1990), 91–100.10.1016/0304-3975(90)90164-DSearch in Google Scholar

[20] M. Jerrum and A. Sinclair, The Markov Chain Monte Carlo method: an approach to approximate counting and integration, in Approximation Algorithms for NP-hard problems, (D. S. Hochbaum ed.) PWS Publishing House, 1995, 482–519.Search in Google Scholar

[21] R. Kannan, P. Tetali and S. Vempala, Simple Markov-chain algorithms for generating bipartite graphs and tournaments, Random Struct. Algorithms, 14 (4) (1999), 293–308.10.1002/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO;2-GSearch in Google Scholar

[22] K. K. Kayibi, S. Pirzada and T. A. Chishti, Sampling contingency tables, AKCE International Journal of Graphs and Combinatorics, in press.Search in Google Scholar

[23] H. Kim, Z. Toroczkai, P. L. Erdős, I. Miklós and L. A. Székely, Degree-based graph construction, J. Phys. A: Math. Theor., 42 (2009), 392001.10.1088/1751-8113/42/39/392001Search in Google Scholar

[24] M. Luby, D. Randall and A. Sinclair, Markov chain algorithms for planar lattice structures, SIAM J. Comput., 31 (1) (2001), 167–192.10.1137/S0097539799360355Search in Google Scholar

[25] B. McKay and N. C. Wormald, Uniform generation of random regular graphs of moderate degree. J. Algorithms, 11 (1) (1990), 52–67.10.1016/0196-6774(90)90029-ESearch in Google Scholar

[26] L. McShine, Random sampling of labeled tournaments, Electron. J. Combin., 7 (2000), #R8.10.37236/1486Search in Google Scholar

[27] I. Miklós, P. L. Erdös and L. Soukup, Towards random uniform sampling of bipartite graphs with given degree sequence, Electron. J. Combin., 20, 1 (2013), P16.10.37236/3028Search in Google Scholar

[28] M. Molloy and B. Reed, A critical point for random graphs with a given degree sequence, Random Struct. Algorithms, 6 (1995), 161–180.10.1002/rsa.3240060204Search in Google Scholar

[29] M. E. J. Newman, A. L. Barabasi and D. J. Watts, The structure and Dynamics of networks (Princeton Studies in Complexity, Princeton UP) (2006) pp 624.Search in Google Scholar

[30] S. Pirzada, An introduction to Graph Theory, Universities Press, Orient-BlackSwan, Hyderabad (2012).Search in Google Scholar

[31] A. Roberts and L. Stone, Island-sharing by archipelago species, Oecologica, 83 (1990), 560–567.10.1007/BF0031721028313193Search in Google Scholar

[32] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Can. J. Math., 9 (1957), 371–377.10.4153/CJM-1957-044-3Search in Google Scholar

[33] A. Sinclair, Convergence rates of Monte Carlo experiments, in Numerical Methods for Polymeric Systems, (S. G. Whittington ed.) IMA volumes, 639–648.Search in Google Scholar

[34] V. V. Vazirani, Approximation algorithms, Springer-Verlag, Berlin, Heildelberg, New York, 2003.10.1007/978-3-662-04565-7Search in Google Scholar

[35] F. Viger and M. Latapy, Efficient and simple generation of random simple connected graphs with prescribed degree sequence, Lecture Notes in Computer Science 3595 (2005), 440–449.10.1007/11533719_45Search in Google Scholar

[36] N. Wormald, Models of random regular graphs, In Surveys in Combonatorics, 1999 (Canterbury), Cambridge University Press, London Math. Soc. Lecture Note Ser. 267, 239–298.10.1017/CBO9780511721335.010Search in Google Scholar