TowardsRandom Uniform Sampling of Bipartite Graphs with given Degree Sequence

[摘要] In this paper we consider a simple Markov chain for bipartite graphs with given degree sequence on $n$ vertices. We show that the mixing time of this Markov chain is bounded above by a polynomial in $n$ in case of half-regular degree sequence. The novelty

[学科分类] 离散数学和组合数学

[关键词] degree sequence;random sampling;multicommodity flow;Sinclair's method;Markov chain