EXPLORATION WITH RETURN OF HIGHLY DYNAMIC NETWORKS

In this paper, we study the necessary and sufficient time to explore with return constantly connected dynamic networks modelled by a dynamic graphs. Exploration with return consists, for an agent operating in a dynamic graph, of visiting all the vertices of the graph and returning to the starting vertex. We show that for constantly connected dynamic graphs based on a ring of sizen,3n-4 time units are necessary and sufficient to explore it. Assuming that the agent knows the dynamics of the graph.