DSpace Repository

Dynamic Ring Exploration with (H,S) View

Show simple item record

dc.contributor.author Gotoh, Tsuyoshi en
dc.contributor.author Sudo, Yuichi en
dc.contributor.author Ooshita, Fukuhito en
dc.contributor.author Masuzawa, Toshimitsu en
dc.date.accessioned 2020-10-28T05:04:30Z en
dc.date.available 2020-10-28T05:04:30Z en
dc.date.issued 2020-06-12 en
dc.identifier.uri http://hdl.handle.net/10061/14130 en
dc.description.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). ja
dc.language.iso en en
dc.publisher MDPI en
dc.relation.isreplacedby https://www.mdpi.com/1999-4893/13/6/141 en
dc.rights © 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/). ja
dc.subject distributed algorithms en
dc.subject dynamic networks en
dc.subject 1-interval connected rings en
dc.subject mobile agent en
dc.subject exploration en
dc.title Dynamic Ring Exploration with (H,S) View en
dc.type.nii Journal Article en
dc.contributor.transcription オオシタ, フクヒト ja
dc.contributor.alternative 大下, 福仁 ja
dc.textversion none en
dc.identifier.eissn 1999-4893 en
dc.identifier.jtitle Algorithms en
dc.identifier.volume 13 en
dc.identifier.issue 6 en
dc.relation.doi 10.3390/a13060141 en
dc.identifier.NAIST-ID 74652124 en


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account