Towards random uniform sampling of bipartite graphs with given degree sequence (Q1953395)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Towards random uniform sampling of bipartite graphs with given degree sequence |
scientific article |
Statements
Towards random uniform sampling of bipartite graphs with given degree sequence (English)
0 references
7 June 2013
0 references
Summary: 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 of our approach lies in the construction of the multicommodity flow in Sinclair's method.
0 references
degree sequence
0 references
random sampling
0 references
multicommodity flow
0 references
sinclair's method
0 references
Markov chain
0 references
