The nearest unvisited vertex walk on random graphs

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.