You are here

The Nearest Unvisited Vertex Walk on Random Graphs

David Aldous
Monday, January 27, 2020 - 2:30pm
Denny 110
We revisit an old topic in algorithms, the deterministic walk on a finite graph-with-edge-lengths which always moves at speed one toward the nearest unvisited vertex, until every vertex is visited.  There is an elementary relation between this cover time and ball-covering (metric entropy) measures.
 For some familiar models of random connected graphs,  this relation
 allows the order of magnitude of the cover time to be deduced easily from first passage percolation estimates.  Obtaining sharper estimates of this cover time remains a challenging problem.
Event Type: 
Event Subcalendar: 
Share