On systematic scan for sampling H-colorings of the path
From MaRDI portal
Publication:3055763
DOI10.1002/rsa.20243zbMath1215.68188arXiv0706.3794OpenAlexW4233831028MaRDI QIDQ3055763
Publication date: 9 November 2010
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0706.3794
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15) Random walks on graphs (05C81)
Cites Work
- Unnamed Item
- Unnamed Item
- Markov chain comparison
- On the complexity of H-coloring
- Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
- Glauber dynamics on trees: Boundary conditions and mixing time
- Glauber dynamics on trees and hyperbolic graphs
- Convergence properties of the Gibbs sampler for perturbations of Gaussians
- Systematic scan for sampling colorings
- On Markov Chains for Randomly H-Coloring a Graph
- Improved bounds for sampling colorings
- Counting independent sets up to the tree threshold
- Markov Chain Monte Carlo Convergence Diagnostics: A Comparative Review
- On Counting Independent Sets in Sparse Graphs
- Non-uniqueness of measures of maximal entropy for subshifts of finite type
- The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
- Fast convergence of the Glauber dynamics for sampling independent sets
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- On Markov Chains for Independent Sets
- Strong Spatial Mixing with Fewer Colors for Lattice Graphs
- Prescribing a System of Random Variables by Conditional Distributions
- Combinatorial criteria for uniqueness of Gibbs measures
- Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
