# Dynamic Ring Exploration with \((H,s)\) View +
###### Abstract  
The researches about a mobile entity (called agent) on dynamic networks have attracted a lot of attention in recent years. Exploration which requires an agent to visit all the nodes in the network is one of the most fundamental problems. While the exploration of dynamic networks with complete information or with no information about network changes has been studied, an agent with partial information about the network changes has not been considered yet despite its practical importance. In this paper, we consider the exploration of dynamic networks by a single agent with partial information about network changes. To the best of our knowledge, this is the very first work to investigate the exploration problem with such partial information. As a first step in this research direction, we focus on 1-interval connected rings as dynamic networks in this paper. We assume that the single agent has partial information called the \((H,S)\) view by which it always knows whether or not each of the links within \(H\) hops is available in each of the next \(S\) time steps. In this setting, we show that \(H+S\geq n\) and \(S\geq\lceil n/2\rceil\) (\(n\) is the size of the network) are necessary and sufficient conditions to explore 1-interval connected rings. Moreover, we investigate the upper and lower bounds of the exploration time. It is proven that the exploration time is \(O(n^{2})\) for \(\lceil n/2\rceil\leq S<2H^{\prime}-1\), \(O(n^{2}/H+nH)\) for \(S\geq\max(\lceil n/2\rceil,2H^{\prime}-1)\), \(O(n^{2}/H+n\log H)\) for \(S\geq n-1\), and \(\Omega(n^{2}/H)\) for any \(S\) where \(H^{\prime}=\min(H,\lfloor n/2\rfloor)\). distributed algorithms; dynamic networks; 1-interval connected rings; mobile agent; exploration +
Footnote †: journal:  
0000-0002-4000-0000][PERSON] 0000-0002-000  
not at the moment [8; 9; 10; 11; 12]. The former one models the situation where the network changes are completely predictable as the public transportation networks in which the network changes are introduced by totally scheduled movements of the nodes. The latter one models the situation where the network changes are caused by unscheduled events, for example, faults or unscheduled movements of the nodes. Although the above two models are plausible and also theoretically important, the intermediate model, i.e., an agent with partial information or, in other words, capability to know link changes within some distance in the near future should be considered due to the following reasons: even in the totally scheduled situation (if exists), computing all the future changes often costs computation time and it is desirable to compute only the necessary information to solve a problem to save computing time or memories; the ability of an agent to monitor whether there are faults or environmental changes roughly depends on the quality (or costs) of its sensor and it can save some costs to compute only the necessary information for a problem. Moreover, such a model is so interesting from a theoretical viewpoint: how the amount of information available for an agent influences the solvability or the time complexity of problems. In this paper, we consider the exploration of dynamic networks by a single agent with partial information about network changes. To the best of our knowledge, this is the very first work to investigate the exploration using such partial information. As a first step in this research direction, we focus on 1-interval connected rings as dynamic networks in this paper. To formalize the concept of partial information and analyze its influences, in this paper, we first propose the \((H,S)\)_view_ such that the agent with the view can see the _link scheduling_ (when and which links disappear or appear) of the links within \(H\) hops from its location for \(S\) time steps from the current time. Then, we consider how the value of \(H\) or \(S\) influences the solvability or the time complexity of the exploration by a single agent of 1-_interval connected rings_ in which at most one link is missing at each time step.