Variable length path coupling

DOI10.1002/RSA.20166zbMATH Open1137.60032OpenAlexW4231320888MaRDI QIDQ5433262FDOQ5433262

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

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

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)

Cites Work

• Randomly coloring graphs of girth at least five
• Title not available (Why is that?)

Cited In (9)

• Fundamentals of Computation Theory
• Metastability in loss networks with dynamic alternative routing
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)