A more rapidly mixing Markov chain for graph colorings
From MaRDI portal
Publication:4705336
DOI<285::AID-RSA6>3.0.CO;2-R 10.1002/(SICI)1098-2418(199810/12)13:3/4<285::AID-RSA6>3.0.CO;2-RzbMath0961.60075OpenAlexW2049712767MaRDI QIDQ4705336
Catherine Greenhill, Martin Dyer
Publication date: 19 December 1999
Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<285::aid-rsa6>3.0.co;2-r
Analysis of algorithms (68W40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Coloring of graphs and hypergraphs (05C15)
Related Items (18)
The generalized distance spectrum of a graph and applications ⋮ Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs ⋮ Algorithms to approximately count and sample conforming colorings of graphs ⋮ Unnamed Item ⋮ Mixing of the Glauber dynamics for the ferromagnetic Potts model ⋮ Sampling from the low temperature Potts model through a Markov chain on flows ⋮ New algorithms and analyses for sum-preserving encryption ⋮ Coupling and self-stabilization ⋮ Path coupling without contraction ⋮ Delayed path coupling and generating random permutations ⋮ Mixing Times of Markov Chains of 2-Orientations ⋮ Sampling and Counting 3-Orientations of Planar Triangulations ⋮ Convergence rates of Markov chains for some self-assembly and non-saturated Ising models ⋮ Rapid mixing for lattice colourings with fewer colours ⋮ Sampling biased monotonic surfaces using exponential metrics ⋮ Polynomial-time counting and sampling of two-rowed contingency tables ⋮ Non-negative Ollivier curvature on graphs, reverse Poincaré inequality, Buser inequality, Liouville property, Harnack inequality and eigenvalue estimates ⋮ On the expected time for Herman's probabilistic self-stabilizing algorithm
This page was built for publication: A more rapidly mixing Markov chain for graph colorings
