The mixing time of Glauber dynamics for coloring regular trees
From MaRDI portal
Publication:3057064
DOI10.1002/rsa.20303zbMath1348.68172OpenAlexW4237804884MaRDI QIDQ3057064
Leslie Ann Goldberg, Mark R. Jerrum, Marek Karpinski
Publication date: 24 November 2010
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20303
Computational methods in Markov chains (60J22) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Randomly coloring planar graphs with fewer colors than the maximum degree, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, Unnamed Item, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, The Glauber dynamics for edge‐colorings of trees, Approximate Counting via Correlation Decay in Spin Systems
Cites Work
- Unnamed Item
- Geometric bounds for eigenvalues of Markov chains
- Markov chain comparison
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Comparison theorems for reversible Markov chains
- Glauber dynamics on trees and hyperbolic graphs
- Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
- Analyzing Glauber dynamics by comparison of Markov chains
- Markov Chain Algorithms for Planar Lattice Structures
- On Counting Independent Sets in Sparse Graphs
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Randomly coloring planar graphs with fewer colors than the maximum degree
- Some Inequalities for Reversible Markov Chains
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Random sampling of 3‐colorings in ℤ2
- Fast mixing for independent sets, colorings, and other models on trees
