We study the computability and complexity of the exploration problem in a
class of highly dynamic graphs: periodically varying (PV) graphs, where the
edges exist only at some (unknown) times defined by the periodic movements of
carriers. These graphs naturally model highly dynamic infrastructure-less
networks such as public transports with fixed timetables, low earth orbiting
(LEO) satellite systems, security guards' tours, etc. We establish necessary
conditions for the problem to be solved. We also derive lower bounds on the
amount of time required in general, as well as for the PV graphs defined by
restricted classes of carriers movements: simple routes, and circular routes.
We then prove that the limitations on computability and complexity we have
established are indeed tight. In fact we prove that all necessary conditions
are also sufficient and all lower bounds on costs are tight. We do so
constructively presenting two worst case optimal solution algorithms, one for
anonymous systems, and one for those with distinct nodes ids. An added benefit
is that the algorithms are rather simple.