Deterministic random walks on finite graphs

DOI10.1002/RSA.20533zbMATH Open1319.05119OpenAlexW2137795931MaRDI QIDQ5265345FDOQ5265345

Shuji Kijima, Kentaro Koga, Kazuhisa Makino

Publication date: 23 July 2015

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20533

Recommendations

• Deterministic random walks on finite graphs
• Deterministic random walks for rapidly mixing chains
• Unbounded discrepancy of deterministic random walks on grids
• Deterministic random walks on the integers
• Deterministic random walks

zbMATH Keywords

random walkrotor-router modelPropp machine

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• The rotor-router shape is spherical
• Simulating a Random Walk with Constant Error
• Deterministic Random Walks on the Two-Dimensional Grid
• Spherical asymptotics for the rotor-router model in $\mathbb{Z}^d$
• The cover time of deterministic random walks
• Internal diffusion limited aggregation
• Goldbug variations
• Subdiffusive fluctuations for internal diffusion limited aggregation
• Deterministic random walks on the integers
• Deterministic random walks on regular trees
• Strong robustness of randomized rumor spreading protocols
• Quasirandom Rumor Spreading on the Complete Graph Is as Fast as Randomized Rumor Spreading
• Quasirandom rumor spreading on expanders
• Introducing Quasirandomness to Computer Science
• Quasirandom rumor spreading

Cited In (14)

• Deterministic random walks on the integers
• Does adding more agents make a difference? A case study of cover time for the rotor-router
• Quasirandomness in Graphs
• Title not available (Why is that?)
• A simple approach for adapting continuous load balancing processes to discrete settings
• Restricted random walks on a graph
• Random walk in a finite directed graph subject to a road coloring
• Title not available (Why is that?)
• Total variation discrepancy of deterministic random walks for ergodic Markov chains
• Unbounded Discrepancy of Deterministic Random Walks on Grids
• Euler Tour Lock-In Problem in the Rotor-Router Model
• Deterministic Random Walks on the Two-Dimensional Grid
• Deterministic Random Walks for Rapidly Mixing Chains
• The cover time of deterministic random walks for general transition probabilities

This page was built for publication: Deterministic random walks on finite graphs

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