The Electronic Journal of Combinatorics · 2013 · 51 citations · 16 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsStochastic ProcessesGraph AlgorithmsGraph TheoryMarkov ChainsMarkov ProcessesNetwork Flow AlgorithmsNetwork FlowsMarkov Chains On GraphsMixing Time AnalysisMixing Time CharacterizationMulticommodity FlowRandom Graph TheoryRandom GraphsRandom SamplingUniform Random Sampling
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.
16
Equation of State Calculations by Fast Computing Machines
N. Metropolis, Arianna W. Rosenbluth, M. N. Rosenbluth et al. · The Journal of Chemical Physics · 1953 · 37.1K citations
Monte Carlo sampling methods using Markov chains and their applications
W. Keith Hastings · Biometrika · 1970 · 15.2K citations
The Structure and Dynamics of Networks
Marián Boguñá · Journal of Statistical Physics · 2007 · 1.5K citations