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

DOI10.1137/S0097539700372708zbMath0999.05035MaRDI QIDQ2719118

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

Publication date: 21 June 2001

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

zbMATH Keywords

Markov chains; graph coloring; Glauber dynamics; coupling; stopping times

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)