TowardsRandom Uniform Sampling of Bipartite Graphs with given Degree Sequence

Electronic Journal Of Combinatorics

István Miklós¹ 

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

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

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

【 授权许可】

Others