Multiple random walks on paths and grids

DOI10.4230/LIPICS.STACS.2017.44MaRDI QIDQ4636644zbMATH OpenFDO

Authors Andrej Ivašković, Adrian Kosowski, Dominik Pajak, Thomas Sauerwald

Publication date 19 April 2018

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2017.44

zbMATH Keywords

parallel computingrandom walksrandomized algorithms

Mathematics Subject Classification ID

Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20)

Recommendations

• Tight Bounds for the Cover Time of Multiple Random Walks
• How Well Do Random Walks Parallelize?
• Many Random Walks Are Faster Than One
• Tight bounds for the cover time of multiple random walks
• On the cover time of random walks on graphs

Cited in

(7)

• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• Tight Bounds for the Cover Time of Multiple Random Walks
• Tight bounds for the cover time of multiple random walks
• Multiple random walks on graphs: mixing few to cover many
• Covering a graph with independent walks
• Collaboration of random walks on graphs
• Multiple random walks on graphs: mixing few to cover many

This page was built for publication: Multiple random walks on paths and grids

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