Conference:
David Aldous (UC Berkeley)
We revisit an old topic in algorithms, the deterministic walk on a connected 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.