Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time
From MaRDI portal
Publication:5175230
DOI10.1002/rsa.20504zbMath1309.05165arXiv1204.1939OpenAlexW2091712762MaRDI QIDQ5175230
Petra Berenbrink, Colin Cooper, Tom Friedetzky
Publication date: 20 February 2015
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.1939
Related Items (5)
The power of two choices for random walks ⋮ The cover time of a biased random walk on a random cubic graph ⋮ Unnamed Item ⋮ The cover time of a biased random walk on a random regular graph of odd degree ⋮ Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk
Cites Work
- Derandomizing random walks in undirected graphs using locally fair exploration strategies
- Ramanujan graphs
- Some sample path properties of a random walk on the cube
- Lower bounds for covering times for reversible Markov chains and random walks on graphs
- A distributed ant algorithm for efficiently patrolling a network
- A Technique for Lower Bounding the Cover Time
- Generating Random Regular Graphs Quickly
- A tight lower bound on the cover time for random walks on graphs
This page was built for publication: Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time
