The Nearest Unvisited Vertex Walk on Random Graphs

2019/12/31 by Aldous, David
#05C80 60K37 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1912.13175

Abstract

We revisit an old minor topic in algorithms, the deterministic walk on a finite graph which always moves toward the nearest unvisited vertex until every vertex is visited. There is an elementary connection between this cover time and ball-covering (metric entropy) measures. For some familiar models of random graphs, this connection allows the order of magnitude of the cover time to be deduced from first passage percolation estimates. Establishing sharper results seems a challenging problem.

Related

• The Cover Time of Random Walks on Graphs
• Many Random Walks Are Faster Than One
• Linear Cover Time is Exponentially Unlikely
• The cover time of a biased random walk on a random cubic graph
• On the Structure and Computation of Random Walk Times in Finite Graphs