Multiple random walks on graphs: mixing few to cover many

DOI10.1017/s0963548322000372zbMath1526.05128arXiv2011.07893OpenAlexW3183332515MaRDI QIDQ6085870

Thomas Sauerwald, John Sylvester, Nicolás Rivera

Publication date: 8 November 2023

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.07893

zbMATH Keywords

Markov chainsmixing timecover timemultiple random walks

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Random walks on graphs (05C81)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the vacant set of random walks on the hypercube and other regular graphs of high degree
• Cover times, blanket times, and majorizing measures
• Mixing and hitting times for finite Markov chains
• Mixing times are hitting times of large sets
• Tight bounds for the cover time of multiple random walks
• Gaussian estimates for Markov chains and random walks on groups
• Simple efficient load-balancing algorithms for peer-to-peer systems
• The cover time of the preferential attachment graph
• Strong uniform times and finite random walks
• Chernoff-type bound for finite Markov chains
• A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
• Frogs on trees?
• On the cover time of random walks on graphs
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• A comparison principle for random walk on dynamical percolation
• Random walks with multiple step lengths
• On certain connectivity properties of the internet topology
• Probability on Trees and Networks
• A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
• Tight bounds on information dissemination in sparse mobile networks
• The Hitting Time of Multiple Random Walks
• How Well Do Random Walks Parallelize?
• Trading Space for Time in Undirected s-t Connectivity
• A tight lower bound on the cover time for random walks on graphs
• Testing Expansion in Bounded-Degree Graphs
• Walking randomly, massively, and efficiently
• Spatial gossip and resource location protocols
• The multi-agent rotor-router on the ring
• Expansion and the cover time of parallel random walks
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Many Random Walks Are Faster Than One
• Random walks and forbidden minors II
• Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding
• Planar graphs: Random walks and bipartiteness testing
• Distributed Random Walks
• Probability and Computing
• Information Dissemination via Random Walks in d-Dimensional Space
• Fast Low-Cost Estimation of Network Properties Using Random Walks
• The power of two choices for random walks
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Multiple random walks on graphs: mixing few to cover many