The cover time of deterministic random walks for general transition probabilities

DOI10.1016/j.tcs.2020.02.009zbMath1440.60039arXiv1602.07729OpenAlexW3005639436MaRDI QIDQ2310755

Takeharu Shiraga

Publication date: 6 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

mixing timecover timerotor-router modelmultiple random walksrotor router modelstack walkmultiple random walk

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)

Cites Work

• Unnamed Item
• Bounds on the cover time of parallel rotor walks
• Tight bounds for the cover time of multiple random walks
• The cover time of deterministic random walks
• The hitting and cover times of Metropolis walks
• The hitting and cover times of random walks on finite graphs using local degree information
• Strong uniform times and finite random walks
• The Chairman assignment problem
• Limit behavior of the multi-agent rotor-router system
• Total variation discrepancy of deterministic random walks for ergodic Markov chains
• A distributed ant algorithm for efficiently patrolling a network
• Deterministic random walks on the integers
• Improved Analysis of Deterministic Load-Balancing Schemes
• Speeding Up Cover Time of Sparse Graphs Using Local Knowledge
• Deterministic random walks on regular trees
• Rotor Walks and Markov Chains
• Quasirandom Load Balancing
• Simulating a Random Walk with Constant Error
• Deterministic Random Walks on the Two-Dimensional Grid
• Euler Tour Lock-In Problem in the Rotor-Router Model
• Trading Space for Time in Undirected s-t Connectivity
• A tight upper bound on the cover time for random walks on graphs
• Random Walks with the Minimum Degree Local Rule Have O(N²) Cover Time
• Deterministic Random Walks for Rapidly Mixing Chains
• A tight lower bound on the cover time for random walks on graphs
• Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router
• Many Random Walks Are Faster Than One
• Deterministic random walks on finite graphs

This page was built for publication: The cover time of deterministic random walks for general transition probabilities