  A mobile agent in a network wants to visit every node of an n-node network,
using a small number of steps. We investigate the performance of the following
``nearest neighbor'' heuristic: always go to the nearest unvisited node. If the
network graph never changes, then from (Rosenkrantz, Stearns and Lewis, 1977)
and (Hurkens and Woeginger, 2004) it follows that Theta(n log n) steps are
necessary and sufficient in the worst case. We give a simpler proof of the
upper bound and an example that improves the best known lower bound.
  We investigate how the performance of this heuristic changes when it is
distributively implemented in a network. Even if network edges are allow to
fail over time, we show that the nearest neighbor strategy never runs for more
than O(n^2) iterations. We also show that any strategy can be forced to take at
least n(n-1)/2 steps before all nodes are visited, if the edges of the network
are deleted in an adversarial way.
