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

couplinggraph coloringMarkov chain

Mathematics Subject Classification ID

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

Recommendations

• Variable length path coupling
• Path coupling without contraction
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• scientific article; zbMATH DE number 1445357
• 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)

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

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)