Dynamic Ring Exploration with (H,S) View
| Autor: | Yuichi Sudo, Toshimitsu Masuzawa, Fukuhito Ooshita, Tsuyoshi Gotoh |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
distributed algorithms
lcsh:T55.4-60.8 0102 computer and information sciences 02 engineering and technology Exploration problem exploration 01 natural sciences Upper and lower bounds lcsh:QA75.5-76.95 Theoretical Computer Science Combinatorics 1-interval connected rings Complete information mobile agent 0202 electrical engineering electronic engineering information engineering lcsh:Industrial engineering. Management engineering Single agent Mathematics Mobile entity Numerical Analysis Ring (mathematics) dynamic networks Computational Mathematics Computational Theory and Mathematics 010201 computation theory & mathematics 020201 artificial intelligence & image processing lcsh:Electronic computers. Computer science |
| Zdroj: | Algorithms, Vol 13, Iss 141, p 141 (2020) Algorithms Volume 13 Issue 6 |
| ISSN: | 1999-4893 |
| Popis: | 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 &ge n and S &ge &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 &le S < 2 H &prime &minus 1 , O ( n 2 / H + n H ) for S &ge max ( &lceil 1 ) , O ( n 2 / H + n log H ) for S &ge n &minus 1 , and &Omega ( n 2 / H ) for any S where H &prime = min ( H , &lfloor n / 2 &rfloor ) . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|