{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T07:26:19Z","timestamp":1780471579260,"version":"3.54.1"},"reference-count":19,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2020,6,12]],"date-time":"2020-06-12T00:00:00Z","timestamp":1591920000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["17K19977"],"award-info":[{"award-number":["17K19977"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["18K11167"],"award-info":[{"award-number":["18K11167"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["20H04140"],"award-info":[{"award-number":["20H04140"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19H04085"],"award-info":[{"award-number":["19H04085"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"name":"JST SICORP","award":["JPMJSC1606"],"award-info":[{"award-number":["JPMJSC1606"]}]},{"name":"JST SICORP","award":["JPMJSC1806"],"award-info":[{"award-number":["JPMJSC1806"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 \u2265 n     and     S \u2265 \u2308 n \/ 2 \u2309     (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      \u2308 n \/ 2 \u2309  \u2264 S &lt; 2  H \u2032  \u2212 1    ,     O (  n 2  \/ H + n H )     for     S \u2265 max (  \u2308 n \/ 2 \u2309  , 2  H \u2032  \u2212 1 )    ,     O (  n 2  \/ H + n log H )     for     S \u2265 n \u2212 1    , and     \u03a9 (  n 2  \/ H )     for any S where      H \u2032  = min  ( H ,  \u230a n \/ 2 \u230b  )     .<\/jats:p>","DOI":"10.3390\/a13060141","type":"journal-article","created":{"date-parts":[[2020,6,12]],"date-time":"2020-06-12T05:02:24Z","timestamp":1591938144000},"page":"141","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Dynamic Ring Exploration with (H,S) View"],"prefix":"10.3390","volume":"13","author":[{"given":"Tsuyoshi","family":"Gotoh","sequence":"first","affiliation":[{"name":"Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuichi","family":"Sudo","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fukuhito","family":"Ooshita","sequence":"additional","affiliation":[{"name":"Nara Institute of Science and Technology, 8916-5 Takayamacho, Ikoma, Nara 630-0101, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4628-6393","authenticated-orcid":false,"given":"Toshimitsu","family":"Masuzawa","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,6,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1080\/17445760.2012.668546","article-title":"Time-varying graphs and dynamic networks","volume":"27","author":"Casteigts","year":"2012","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Das, S. (2019). Graph explorations with mobile agents. Distributed Computing by Mobile Entities, Springer.","DOI":"10.1007\/978-3-030-11072-7_16"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Hoffmann, M., and Kammer, F. (2015, January 6\u201310). On temporal graph exploration. Proceedings of the International Colloquium on Automata, Languages, and Programming, Kyoto, Japan.","DOI":"10.1007\/978-3-662-47672-7_36"},{"key":"ref_4","unstructured":"Erlebach, T., Kammer, F., Luo, K., Sajenko, A., and Spooner, J.T. (2019, January 9\u201312). Two moves per time step make a difference. Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece."},{"key":"ref_5","unstructured":"Erlebach, T., and Spooner, J.T. (2018, January 27\u201331). Faster exploration of degree-bounded temporal graphs. Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ilcinkas, D., Klasing, R., and Wade, A.M. (2014, January 23\u201325). Exploration of constantly connected dynamic graphs based on cactuses. Proceedings of the International Colloquium on Structural Information and Communication Complexity, Takayama, Japan.","DOI":"10.1007\/978-3-319-09620-9_20"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1144","DOI":"10.1007\/s00224-017-9796-3","article-title":"Exploration of the T-interval-connected dynamic graphs: The case of the ring","volume":"62","author":"Ilcinkas","year":"2018","journal-title":"Theory Comput. Syst."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Bournat, M., Datta, A.K., and Dbois, S. (2016, January 7\u201310). Self-stabilizing robots in highly dynamic environments. Proceedings of the International Synposium on Stabilization, Safety, and Security of Distributed Systems, Lyon, France.","DOI":"10.1007\/978-3-319-49259-9_5"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Bournat, M., Dubois, S., and Petit, F. (2017, January 5\u20138). Computability of perpetual exploration in highly dynamic rings. Proceedings of the IEEE 37th International Conference on Distributed Computing Systems, Atlanta, GA, USA.","DOI":"10.1109\/ICDCS.2017.80"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Di Luna, G.A., Dobrev, S., Flocchini, P., and Santoro, N. (2018). Distributed exploration of dynamic rings. Distrib. Comput., 1\u201327.","DOI":"10.1007\/s00446-018-0339-1"},{"key":"ref_11","unstructured":"Gotoh, T., Flocchini, P., Masuzawa, T., and Santoro, N. (2020, January 17\u201319). Tight bounds on distributed exploration of temporal graphs. Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), Neuchatel, Switzerland."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Gotoh, T., Sudo, Y., Ooshita, F., Kakugawa, H., and Masuzawa, T. (2018, January 2\u20135). Group Exploration of Dynamic Tori. Proceedings of the IEEE 38th International Conference on Distributed Computing Systems, Vienna, Austria.","DOI":"10.1109\/ICDCS.2018.00080"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.tcs.2018.10.018","article-title":"Gathering in dynamic rings","volume":"811","author":"Flocchini","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Das, S., Di Luna, G.A., and Gasieniec, L.A. (2019, January 20\u201324). Patrolling on dynamic ring networks. Proceedings of the International Conference on Current Trends in Theory and Practice of Informatics, Limassol, Cyprus.","DOI":"10.1007\/978-3-030-10801-4_13"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Das, S., Di Luna, G., Pagli, L., and Prencipe, G. (2019, January 13\u201316). Compacting and Grouping Mobile Agents on Dynamic Rings. Proceedings of the International Conference on Theory and Applications of Models of Computation, Kitakyushu, Japan.","DOI":"10.1007\/978-3-030-14812-6_8"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1145\/1959045.1959064","article-title":"Dynamic networks: Models and algorithms","volume":"42","author":"Kuhn","year":"2011","journal-title":"ACM SIGACT News"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Di Luna, G.A. (2019). Mobile Agents on Dynamic Graphs. Distributed Computing by Mobile Entities, Springer.","DOI":"10.1007\/978-3-030-11072-7_20"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Agarwalla, A., Augustine, J., Moses, W.K., Madhav, S.K., and Sridhar, A.K. (2018, January 4\u20137). Deterministic dispersion of mobile robots in dynamic rings. Proceedings of the 19th International Conference on Distributed Computing and Networking, Varanasi, India.","DOI":"10.1145\/3154273.3154294"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Gotoh, T., Sudo, Y., Ooshita, F., and Masuzawa, T. (2019, January 22\u201325). Exploration of Dynamic Ring Networks by a Single Agent with the H-hops and S-time Steps View. Proceedings of the International Symposium on Stabilizing, Safety, and Security of Distributed Systems, Pisa, Italy.","DOI":"10.1007\/978-3-030-34992-9_14"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/6\/141\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:38:08Z","timestamp":1760175488000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/6\/141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,12]]},"references-count":19,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2020,6]]}},"alternative-id":["a13060141"],"URL":"https:\/\/doi.org\/10.3390\/a13060141","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,12]]}}}