Variable length path coupling

DOI10.1002/RSA.20166MaRDI QIDQ5433262zbMATH OpenOpenAlexFDO

Authors Thomas P. Hayes, Eric Vigoda

Publication date 8 January 2008

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.5562

zbMATH Keywords

Markov chaincouplinggraph coloring

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Variable length path coupling
• Path coupling without contraction
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Publication:4952676
• A more rapidly mixing Markov chain for graph colorings

Cites work

• scientific article; zbMATH DE number 1303575 (Why is no real title available?)
• Randomly coloring graphs of girth at least five

Cited in

(9)

• Fundamentals of Computation Theory
• Metastability in loss networks with dynamic alternative routing
• scientific article; zbMATH DE number 1445357 (Why is no real title available?)
• scientific article; zbMATH DE number 1563189 (Why is no real title available?)
• Segregating Markov chains
• Randomly coloring constant degree graphs
• Attracting random walks
• Variable length path coupling
• Path coupling without contraction

This page was built for publication: Variable length path coupling

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