Multiple random walks on graphs: mixing few to cover many
From MaRDI portal
Publication:6085870
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
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
