Deterministic random walks on finite graphs

DOI10.1002/RSA.20533MaRDI QIDQ5265345zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

random walkrotor-router modelPropp machine

Mathematics Subject Classification ID

Random walks on graphs (05C81)

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

Cites work

• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• Deterministic random walks on regular trees
• Deterministic random walks on the integers
• Deterministic random walks on the two-dimensional grid
• Goldbug variations
• Internal diffusion limited aggregation
• Introducing Quasirandomness to Computer Science
• Quasirandom rumor spreading on expanders
• Quasirandom rumor spreading on the complete graph is as fast as randomized rumor spreading
• Quasirandom rumor spreading, an experimental analysis
• Simulating a Random Walk with Constant Error
• Spherical asymptotics for the rotor-router model in $\mathbb{Z}^d$
• Strong robustness of randomized rumor spreading protocols
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• Subdiffusive fluctuations for internal diffusion limited aggregation
• The rotor-router shape is spherical

Cited in

(21)

• 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
• Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
• scientific article; zbMATH DE number 5763161 (Why is no real title available?)
• Discrete analog computing with rotor-routers
• Deterministic random walks for rapidly mixing chains
• Deterministic random walks on finite graphs
• A simple approach for adapting continuous load balancing processes to discrete settings
• Restricted random walks on a graph
• Deterministic walks with choice
• Random walk in a finite directed graph subject to a road coloring
• Unbounded discrepancy of deterministic random walks on grids
• Unbounded discrepancy of deterministic random walks on grids
• Rotor walks and Markov chains
• Limit behavior of the multi-agent rotor-router system
• Total variation discrepancy of deterministic random walks for ergodic Markov chains
• scientific article; zbMATH DE number 7650109 (Why is no real title available?)
• Total variation discrepancy of deterministic random walks for ergodic Markov chains
• Euler Tour Lock-In Problem in the Rotor-Router Model
• Deterministic Random Walks on the Two-Dimensional Grid

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)