Exploration of the <italic>T</italic>-Interval-Connected Dynamic Graphs: the Case of the Ring.

In this paper, we study the <italic>T</italic>-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is <italic>T</italic>-interval-connected (<italic>T</italic> ≥ 1) if, for every window of <italic>T</italic> consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. <xref>14</xref>) (STOC 2010). We focus on the case when the underlying graph is a ring of size <italic>n</italic>, and we show that the worst-case time complexity for the exploration problem is 2<italic>n</italic> − <italic>T</italic> − Θ(1) time units if the agent knows the dynamics of the graph, and n+nmax{1,T−1}(δ−1)±Θ(δ)<inline-graphic></inline-graphic> time units otherwise, where <italic>δ</italic> is the maximum time between two successive appearances of an edge. [ABSTRACT FROM AUTHOR]