A note on the Glauber dynamics for sampling independent sets
From MaRDI portal
Publication:1594581
zbMath0967.68172MaRDI QIDQ1594581
Publication date: 8 February 2001
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/121186
60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
68W20: Randomized algorithms
Related Items
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Cutoff for General Spin Systems with Arbitrary Boundary Conditions, Gibbs rapidly samples colorings of \(G(n, d/n)\), Coupling with the stationary distribution and improved sampling for colorings and independent sets, On the hardness of sampling independent sets beyond the tree threshold, Glauber dynamics on trees: Boundary conditions and mixing time, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, A probabilistic approach to convex \((\phi)\)-entropy decay for Markov chains, Correlation decay for hard spheres via Markov chains, Logarithmic Sobolev inequalities for finite spin systems and applications, Spatial mixing and the connective constant: optimal bounds, A general lower bound for mixing of single-site dynamics on graphs, Rapid mixing of Gibbs sampling on graphs that are sparse on average, Exponential Time Complexity of Weighted Counting of Independent Sets, Sampling Edge Covers in 3-Regular Graphs