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 n and S dn/2e (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(n2) for dn/2e S < 2H0 1,
O(n2/H + nH) for S max(dn/2e, 2H0 1), O(n2/H + n log H) for S n 1, and W(n2/H) for
any S where H0 = min(H, bn/2c).