{"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":1780471579264,"version":"3.54.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s00224-020-10001-0","type":"journal-article","created":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T12:05:02Z","timestamp":1597406702000},"page":"257-273","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Exploration of Dynamic Cactuses with Sub-logarithmic Overhead"],"prefix":"10.1007","volume":"65","author":[{"given":"David","family":"Ilcinkas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5920-8402","authenticated-orcid":false,"given":"Ahmed M.","family":"Wade","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,8,14]]},"reference":[{"key":"10001_CR1","doi-asserted-by":"crossref","unstructured":"Aaron, E., Krizanc, D., Meyerson, E.: DMVP: foremost waypoint coverage of time-varying graphs. In: 40th international workshop on graph-theoretic concepts in computer science (WG), LNCS, vol. 8147, pp 29\u201341 (2014)","DOI":"10.1007\/978-3-319-12340-0_3"},{"key":"10001_CR2","doi-asserted-by":"crossref","unstructured":"Aaron, E., Krizanc, D., Meyerson, E.: Multi-robot foremost coverage of time-varying graphs. In: 10th international symposium on algorithms and experiments for sensor systems, wireless networks and distributed robotics (ALGOSENSORS), LNCS, vol. 8847, pp 22\u201338 (2014)","DOI":"10.1007\/978-3-662-46018-4_2"},{"key":"10001_CR3","doi-asserted-by":"crossref","unstructured":"Agarwalla, A., Augustine, J., Moses, W.K. Jr, Madhav, S.K., Sridhar, A.K.: Deterministic dispersion of mobile robots in dynamic rings. In: 19th international conference on distributed computing and networking, ICDCN 2018, pp 19:1\u201319:4 (2018)","DOI":"10.1145\/3154273.3154294"},{"key":"10001_CR4","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.ipl.2018.10.016","volume":"142","author":"HL Bodlaender","year":"2019","unstructured":"Bodlaender, H.L., van der Zanden, T.C.: On exploring always-connected temporal graphs of small pathwidth In. Inform Process Lett 142, 68\u201371 (2019)","journal-title":"Inform Process Lett"},{"key":"10001_CR5","doi-asserted-by":"crossref","unstructured":"Bournat, M., Dubois, S., Petit, F: Computability of perpetual exploration in highly dynamic rings. In: 37th IEEE international conference on distributed computing systems (ICDCS), IEEE computer society, pp 794\u2013804 (2017)","DOI":"10.1109\/ICDCS.2017.80"},{"issue":"3","key":"10001_CR6","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02684332","volume":"60","author":"R Burkard","year":"1998","unstructured":"Burkard, R., Krarup, J.: A linear algorithm for the Pos\/Neg-Weighted 1-Median problem on a cactus. In Comput 60(3), 193\u2013216 (1998)","journal-title":"In Comput"},{"issue":"5","key":"10001_CR7","first-page":"387","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. In: Int J Parall, Emerg Distrib Syst 27 (5), 387\u2013408 (2012)","journal-title":"In: Int J Parall, Emerg Distrib Syst"},{"key":"10001_CR8","doi-asserted-by":"crossref","unstructured":"Das, S., Di Luna, G.A., Gasieniec, L.A.: Patrolling on dynamic ring networks. In: 45th international conference on current trends in theory and practice of computer science (SOFSEM), LNCS, vol. 11376, pp 150\u2013163 (2019)","DOI":"10.1007\/978-3-030-10801-4_13"},{"issue":"1","key":"10001_CR9","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00446-018-0339-1","volume":"33","author":"GA Di Luna","year":"2020","unstructured":"Di Luna, G.A., Dobrev, S., Flocchini, P., Santoro, N.: Distributed exploration of dynamic rings. Distribut Comput 33(1), 41\u201367 (2020)","journal-title":"Distribut Comput"},{"key":"10001_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.tcs.2018.10.018","volume":"811","author":"GA Di Luna","year":"2020","unstructured":"Di Luna, G.A., Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Viglietta, G.: Gathering in dynamic rings. In theoretical computer science 811, 79\u201398 (2020)","journal-title":"In theoretical computer science"},{"key":"10001_CR11","doi-asserted-by":"crossref","unstructured":"Dutta, C., Pandurangan, G., Rajaraman, R., Sun, Z., Viola, E.: On the complexity of information spreading in dynamic networks. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms (SODA), pp 717\u2013736 (2013)","DOI":"10.1137\/1.9781611973105.52"},{"key":"10001_CR12","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: 42nd international colloquium on automata, languages, and programming (ICALP), LNCS, vol. 9134, pp 444\u2013455 (2015)","DOI":"10.1007\/978-3-662-47672-7_36"},{"key":"10001_CR13","unstructured":"Erlebach, T., Spooner, J.T.: Faster exploration of degree-bounded temporal graphs. In: 43rd international symposium on mathematical foundations of computer science (MFCS), pp 36:1\u201336:13 (2018)"},{"key":"10001_CR14","unstructured":"Ferreira, A.: Building a reference combinatorial model for dynamic networks: initial results in evolving graphs. INRIA RR-5041 (2003)"},{"key":"10001_CR15","unstructured":"Gotoh, T., Flocchini, P., Masuzawa, Santoro, N: Tight bounds on distributed exploration of temporal graphs. In: 23rd international conference on principles of distributed systems (OPODIS), vol. 153, pp 22:1\u201322:16 (2019)"},{"key":"10001_CR16","doi-asserted-by":"crossref","unstructured":"Gotoh, T., Sudo, Y., Ooshita, F., Kakugawa, H., Masuzawa, T.: Group Exploration of Dynamic Tori. In: 38th IEEE international conference on distributed computing systems (ICDCS), IEEE computer society, pp 775\u2013785 (2018)","DOI":"10.1109\/ICDCS.2018.00080"},{"issue":"6","key":"10001_CR17","doi-asserted-by":"publisher","first-page":"141","DOI":"10.3390\/a13060141","volume":"13","author":"T Gotoh","year":"2020","unstructured":"Gotoh, T., Sudo, Y., Ooshita, F., Masuzawa, T.: Dynamic Ring Exploration with (H,S) View In. Algorithms 13(6), 141 (2020)","journal-title":"Algorithms"},{"key":"10001_CR18","doi-asserted-by":"crossref","unstructured":"Ilcinkas, D., Klasing, R., Wade, A.M.: Exploration of constantly connected dynamic graphs based on cactuses. In: 21st international colloquium on structural information and communication complexity (SIROCCO), LNCS, vol. 8576, pp 250\u2013262 (2014)","DOI":"10.1007\/978-3-319-09620-9_20"},{"key":"10001_CR19","doi-asserted-by":"crossref","unstructured":"Ilcinkas, D., Wade, A.M.: Exploration of the T-Interval-Connected dynamic graphs: the case of the ring. In: Theory of Computing Systems, vol. 62, pp 1144\u20131160 (2018)","DOI":"10.1007\/s00224-017-9796-3"},{"key":"10001_CR20","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N.A., oshman, R: Distributed computation in dynamic networks. In: 42nd ACM symposium on theory of computing (STOC), pp 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"issue":"1","key":"10001_CR21","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1145\/1959045.1959064","volume":"42","author":"F Kuhn","year":"2011","unstructured":"Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. In ACM SIGACT News 42(1), 82\u201396 (2011)","journal-title":"In ACM SIGACT News"},{"issue":"4","key":"10001_CR22","first-page":"239","volume":"12","author":"O Michail","year":"2016","unstructured":"Michail, O.: An introduction to temporal graphs: an algorithmic perspective. In Int Math 12(4), 239\u2013280 (2016)","journal-title":"In Int Math"},{"key":"10001_CR23","doi-asserted-by":"crossref","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: Theoretical Computer Science, vol. 634, pp 1\u201323 (2016)","DOI":"10.1016\/j.tcs.2016.04.006"},{"key":"10001_CR24","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: DIALM-POMC, pp 104\u2013110 (2005)","DOI":"10.1145\/1080810.1080828"},{"key":"10001_CR25","unstructured":"Shannon, C.E.: Presentation of a maze-solving machine. In: 8th Conference of the Josiah Macy Jr. Found. (Cybernetics), pp 173\u2013180 (1951)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10001-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-10001-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10001-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T23:03:44Z","timestamp":1667775824000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-10001-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,14]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10001"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10001-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,14]]},"assertion":[{"value":"14 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}