An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings

DOI10.1137/S0097539700372708zbMath0999.05035MaRDI QIDQ2719118

Catherine Greenhill, Leslie Ann Goldberg, Martin Dyer, Mark R. Jerrum, Michael Mitzenmacher

Publication date: 21 June 2001

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Markov chainsgraph coloringGlauber dynamicscouplingstopping times

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs ⋮ A general lower bound for mixing of single-site dynamics on graphs ⋮ Systematic scan for sampling colorings

This page was built for publication: An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings