Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time

DOI10.1137/17M1119901zbMath1391.05233OpenAlexW2805389667MaRDI QIDQ3176187

Roee David, Uriel Feige

Publication date: 19 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1119901

zbMATH Keywords

reversible Markov chainminimum weight spanning treecyclic cover timelocally biased random walk

Mathematics Subject Classification ID

Trees (05C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Signed and weighted graphs (05C22) Random walks on graphs (05C81)

Related Items

Reversible random walks on dynamic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Random walks and the effective resistance of networks
• The hitting and cover times of Metropolis walks
• The hitting and cover times of random walks on finite graphs using local degree information
• Covering problems for Brownian motion on spheres
• The electrical resistance of a graph captures its commute and cover times
• On the cover time of random walks on graphs
• Speeding Up Cover Time of Sparse Graphs Using Local Knowledge
• Collisions Among Random Walks on a Graph
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• 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
• Random Walks on Regular and Irregular Graphs