Greedy Random Walk

DOI10.1017/S0963548313000552zbMath1286.05159arXiv1101.5711MaRDI QIDQ5410258

Igor Shinkar, Tal Orenshtein

Publication date: 16 April 2014

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

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

zbMATH Keywords

discrete time self-interacting random process on graphs

Mathematics Subject Classification ID

60K35: Interacting random processes; statistical mechanics type models; percolation theory

05C85: Graph algorithms (graph-theoretic aspects)

05C81: Random walks on graphs

Related Items

Unnamed Item, The cover time of a biased random walk on a random cubic graph, Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk, The power of two choices for random walks, Deterministic walks with choice, Once reinforced random walk on \(\mathbb{Z}\times\gamma\), The cover time of a biased random walk on a random regular graph of odd degree

Cites Work

• Random walk covering of some special trees
• A survey of random processes with reinforcement
• Recurrence properties of Lorentz lattice gas cellular automata
• Excited random walk
• Bounds on the cover time
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Linear cover time is exponentially unlikely
• The power of choice in random walks: An empirical study
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Expander graphs and their applications
• A tight lower bound on the cover time for random walks on graphs
• Self-Avoiding Walks on Hyperbolic Graphs