Sampling k-partite graphs with a given degree sequence

The authors in the paper [15] presented an algorithm that generates uniformly all the bipartite realizations and the other algorithm that generates uniformly all the simple bipartite realizations whenever A is a bipartite degree sequence of a simple graph. The running time of both algorithms is 𝒪(m),where m=12∑i=1nai${\rm{m}} = {1 \over 2}\sum\nolimits_{\rm {i} = 1}^n {{ \rm{a}_\rm {i}}}$. Let A =(A₁ : A₂ : ... : A_k) be a k-partite degree sequence of a simple graph, where A_i has n_i entries such that ∑n_i=n. In the present article, we give a generalized algorithm that generates uniformly all the k-partite realizations of A and another algorithm that generates uniformly all the simple k-partite realizations of A. The running time of both algorithms is 𝒪(m), where m=12∑i=1nai$m = {1 \over 2}\sum\nolimits_{i = 1}^n {{a_i}}$.