scientific article; zbMATH DE number 1445357

MaRDI QIDQ4952676zbMATH OpenFDO

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

Publication date 23 October 2000

zbMATH Keywords

path couplingmixing time of Markov chainsGlauber dynamics for graph colourings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• An extension of path coupling and its application to the Glauber dynamics for graph colorings
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Variable length path coupling

Cited in

(6)

• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• An extension of path coupling and its application to the Glauber dynamics for graph colorings
• Mixing and concentration by Ricci curvature
• Randomly coloring graphs with lower bounds on girth and maximum degree
• Variable length path coupling
• Variable length path coupling

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4952676)