Sampling k-partite graphs with a given degree sequence
Koko Kalambay Kayibi, Uma Tul Samee, S. Pirzada, Muhammad Ali Khan · Acta Universitatis Sapientiae Informatica · 2018
Abstract 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 = 1 2 ∑ i = 1 n a i ${\rm{m}} = {1 \over 2}\sum olimits_{\rm {i} = 1}^n {{ \rm{a}_\rm {i}}}$ . Let A =(A1 : A2 : ... : Ak) be a k-partite degree sequence of a simple graph, where Ai has ni entries such that ∑ni=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 = 1 2 ∑ i = 1 n a i $m = {1 \over 2}\sum olimits_{i = 1}^n {{a_i}}$ .