{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T17:36:58Z","timestamp":1732037818018},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,8,20]],"date-time":"2018-08-20T00:00:00Z","timestamp":1534723200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006109","name":"VEGA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006109","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00446-018-0339-1","type":"journal-article","created":{"date-parts":[[2018,8,20]],"date-time":"2018-08-20T15:27:34Z","timestamp":1534778854000},"page":"41-67","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Distributed exploration of dynamic rings"],"prefix":"10.1007","volume":"33","author":[{"given":"G.","family":"Di Luna","sequence":"first","affiliation":[]},{"given":"S.","family":"Dobrev","sequence":"additional","affiliation":[]},{"given":"P.","family":"Flocchini","sequence":"additional","affiliation":[]},{"given":"N.","family":"Santoro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,20]]},"reference":[{"issue":"4","key":"339_CR1","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1137\/S009753979732428X","volume":"29","author":"S Albers","year":"2000","unstructured":"Albers, S., Henzinger, M.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"key":"339_CR2","first-page":"23","volume-title":"Lecture Notes in Computer Science","author":"Luciana Arantes","year":"2013","unstructured":"Arantes, L., Greve, F., Sens, P., Simon, V.: Eventual leader election in evolving mobile networks. In: Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS), pp. 23\u201337 (2013)"},{"key":"339_CR3","doi-asserted-by":"crossref","unstructured":"Augustine, J., Pandurangan, G., Robinson, P.: Fast byzantine agreement in dynamic networks. In: Proceedings of the 32th Symposium on Principles of Distributed Computing (PODC), pp. 74\u201383 (2013)","DOI":"10.1145\/2484239.2484275"},{"key":"339_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-540-70575-8_11","volume-title":"Automata, Languages and Programming","author":"Chen Avin","year":"2008","unstructured":"Avin, C., Koucky, M., Lotker, Z.: How to explore a fast-changing world. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pp. 121\u2013132 (2008)"},{"key":"339_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Even, S.: Efficient and reliable broadcast is achievable in an eventually connected network. In: Proceedings of the 3th Symposium on Principles of Distributed Computing (PODC), pp. 278\u2013281 (1984)","DOI":"10.1145\/800222.806754"},{"key":"339_CR6","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.tcs.2014.07.013","volume":"610","author":"B Balamohan","year":"2016","unstructured":"Balamohan, B., Dobrev, S., Flocchini, P., Santoro, N.: Exploring an unknown dangerous graph with a constant number of tokens. Theor. Comput. Sci. 610, 169\u2013181 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"339_CR7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00446-011-0133-9","volume":"24","author":"H Baumann","year":"2011","unstructured":"Baumann, H., Crescenzi, P., Fraigniaud, P.: Parsimonious flooding in dynamic graphs. Distrib. Comput. 24(1), 31\u201344 (2011)","journal-title":"Distrib. Comput."},{"key":"339_CR8","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-31104-8_7","volume-title":"Structural Information and Communication Complexity","author":"Martin Biely","year":"2012","unstructured":"Biely, M., Robinson, P., Schmid, U.: Agreement in directed dynamic networks. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 73\u201384 (2012)"},{"key":"339_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.tcs.2013.01.025","volume":"509","author":"B Brejova","year":"2013","unstructured":"Brejova, B., Dobrev, S., Kralovic, R., Vinar, T.: Efficient routing in carrier-based mobile networks. Theor. Comput. Sci. 509, 113\u2013121 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"339_CR10","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"B Bui-Xuan","year":"2003","unstructured":"Bui-Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(2), 267\u2013285 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"339_CR11","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1109\/TC.2012.208","volume":"63","author":"A Casteigts","year":"2014","unstructured":"Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Measuring temporal lags in delay-tolerant networks. IEEE Trans. Comput. 63(2), 397\u2013410 (2014)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"339_CR12","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1142\/S0129054115500288","volume":"25","author":"A Casteigts","year":"2015","unstructured":"Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Shortest, fastest, and foremost broadcast in dynamic networks. Int. J. Found. Comput. Sci. 25(4), 499\u2013522 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5","key":"339_CR13","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"issue":"1","key":"339_CR14","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2008.02.006","volume":"399","author":"J Chalopin","year":"2008","unstructured":"Chalopin, J.: Election and rendezvous with incomparable labels. Theor. Comput. Sci. 399(1), 54\u201370 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"9","key":"339_CR15","doi-asserted-by":"publisher","first-page":"1425","DOI":"10.1109\/TPDS.2011.33","volume":"22","author":"A Clementi","year":"2011","unstructured":"Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Information spreading in stationary Markovian evolving graphs. IEEE Trans. Parallel Distrib. Syst. 22(9), 1425\u20131432 (2011)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"339_CR16","first-page":"320","volume-title":"Lecture Notes in Computer Science","author":"Colin Cooper","year":"2006","unstructured":"Cooper, C., Klasing, R., Radzi, T.: Searching for black-hole faults in a network using multiple agents. In: Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS), pp. 320\u2013332 (2006)"},{"issue":"1\u20133","key":"339_CR17","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2007.05.011","volume":"385","author":"S Das","year":"2007","unstructured":"Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theor. Comput. Sci. 385(1\u20133), 34\u201348 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"339_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8","volume":"32","author":"X Deng","year":"1999","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265\u2013297 (1999)","journal-title":"J. Graph Theory"},{"key":"339_CR19","doi-asserted-by":"crossref","unstructured":"Di Luna, G., Baldoni, R.: Brief announcement: investigating the cost of anonymity on dynamic networks. In: Proceedings of the 34th Symposium on Principles of Distributed Computing (PODC), pp. 339\u2013341 (2015)","DOI":"10.1145\/2767386.2767442"},{"key":"339_CR20","doi-asserted-by":"crossref","unstructured":"Di Luna, G., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Conscious and unconscious counting on anonymous dynamic networks. In: Proceedings of the 15th International Conference on Distributed Computing and Networking (ICDCN), pp. 257\u2013271 (2014)","DOI":"10.1007\/978-3-642-45249-9_17"},{"key":"339_CR21","doi-asserted-by":"crossref","unstructured":"Di\u00a0Luna, G., Dobrev, S., Flocchini, P., Santoro, N.: Live exploration of dynamic rings. In: Proceedings of the 36th IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 570\u2013579 (2016)","DOI":"10.1109\/ICDCS.2016.59"},{"key":"339_CR22","doi-asserted-by":"crossref","unstructured":"Di\u00a0Luna, G., Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Viglietta, G.: Gathering in dynamic rings. In: Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 339\u2013355 (2017)","DOI":"10.1007\/978-3-319-72050-0_20"},{"issue":"2","key":"339_CR23","first-page":"10:1","volume":"11","author":"Y Dieudonn","year":"2014","unstructured":"Dieudonn, Y., Pelc, A.: Deterministic network exploration by anonymous silent agents with local traffic reports. ACM Trans. Algorithms 11(2), 10:1\u201310:29 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"339_CR24","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2012.11.022","volume":"472","author":"S Dobrev","year":"2013","unstructured":"Dobrev, S., Flocchini, P., Kralovic, R., Santoro, N.: Exploring a dangerous unknown graph using tokens. Theor. Comput. Sci. 472, 28\u201345 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"339_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00446-006-0154-y","volume":"19","author":"S Dobrev","year":"2006","unstructured":"Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: optimal mobile agents protocolss. Distrib. Comput. 19(1), 1\u201319 (2006)","journal-title":"Distrib. Comput."},{"key":"339_CR26","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-662-47672-7_36","volume-title":"Automata, Languages, and Programming","author":"Thomas Erlebach","year":"2015","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: Proceedings of 42th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 444\u2013455 (2015)"},{"issue":"5","key":"339_CR27","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1109\/MNET.2004.1337732","volume":"18","author":"A Ferreira","year":"2004","unstructured":"Ferreira, A.: Building a reference combinatorial model for MANETs. IEEE Netw. 18(5), 24\u201329 (2004)","journal-title":"IEEE Netw."},{"key":"339_CR28","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Kellett, M., Mason, P., Santoro, N.: Map construction and exploration by mobile agents scattered in a dangerous network. In: Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1\u201310 (2009)","DOI":"10.1109\/IPDPS.2009.5161080"},{"issue":"1","key":"339_CR29","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/s00224-011-9341-8","volume":"50","author":"P Flocchini","year":"2012","unstructured":"Flocchini, P., Kellett, M., Mason, P., Santoro, N.: Searching for black holes in subways. Theory Comput. Syst. 50(1), 158\u2013184 (2012)","journal-title":"Theory Comput. Syst."},{"key":"339_CR30","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2012.10.029","volume":"469","author":"P Flocchini","year":"2013","unstructured":"Flocchini, P., Mans, B., Santoro, N.: On the exploration of time-varying networks. Theor. Comput. Sci. 469, 53\u201368 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"339_CR31","doi-asserted-by":"publisher","DOI":"10.2200\/S00440ED1V01Y201208DCT010","volume-title":"Distributed Computing by Oblivious Mobile Robots","author":"P Flocchini","year":"2012","unstructured":"Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan & Claypool, San Rafael (2012)"},{"issue":"2\u20133","key":"339_CR32","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.tcs.2005.07.014","volume":"345","author":"P Fraigniaud","year":"2005","unstructured":"Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2\u20133), 331\u2013344 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"339_CR33","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/978-3-662-46018-4_6","volume-title":"Algorithms for Sensor Systems","author":"Emmanuel Godard","year":"2015","unstructured":"Godard, E., Mazauric, D.: Computing the dynamic diameter of non-deterministic dynamic networks is hard. In: Proceedings of the 10th Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGSENSORS), pp. 88\u2013102 (2014)"},{"issue":"7","key":"339_CR34","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0895-7177(97)00050-2","volume":"25","author":"F Harary","year":"1997","unstructured":"Harary, F., Gupta, G.: Dynamic graph models. Math. Comput. Model. 25(7), 79\u201388 (1997)","journal-title":"Math. Comput. Model."},{"key":"339_CR35","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-319-09620-9_20","volume-title":"Structural Information and Communication Complexity","author":"David Ilcinkas","year":"2014","unstructured":"Ilcinkas, D., Klasing, R., Wade, A.: Exploration of constantly connected dynamic graphs based on cactuses. In: Proceedings of the 21st International Colloquium Structural Information and Communication Complexity (SIROCCO), pp. 250\u2013262 (2014)"},{"key":"339_CR36","first-page":"451","volume-title":"Lecture Notes in Computer Science","author":"David Ilcinkas","year":"2011","unstructured":"Ilcinkas, D., Wade, A.: On the power of waiting when exploring public transportation systems. In: Proceedings of the 15th International Conference on Principles of Distributed Systems (OPODIS), pp. 451\u2013464 (2011)"},{"key":"339_CR37","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-319-03578-9_2","volume-title":"Structural Information and Communication Complexity","author":"David Ilcinkas","year":"2013","unstructured":"Ilcinkas, D., Wade, A.: Exploration of the t-interval-connected dynamic graphs: the case of the ring. In: Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 13\u201323 (2013)"},{"key":"339_CR38","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42th Symposium on Theory of Computing (STOC), pp. 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"339_CR39","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moses, Y., Oshman, R.: Coordinated consensus in dynamic networks. In: Proceedings 30th Symposium on Principles of Distributed Computing (PODC), pp. 1\u201310 (2011)","DOI":"10.1145\/1993806.1993808"},{"issue":"9","key":"339_CR40","doi-asserted-by":"publisher","first-page":"1325","DOI":"10.1109\/TPDS.2008.218","volume":"20","author":"C Liu","year":"2009","unstructured":"Liu, C., Wu, J.: Scalable routing in cyclic mobile networks. IEEE Trans. Parallel Distrib. Syst. 20(9), 1325\u20131338 (2009)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"339_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.006","volume":"634","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theor. Comput. Sci. 634, 1\u201323 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"339_CR42","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 104\u2013110 (2005)","DOI":"10.1145\/1080810.1080828"},{"key":"339_CR43","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1006\/jagm.1999.1043","volume":"33","author":"P Panaite","year":"1999","unstructured":"Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33, 281\u2013295 (1999)","journal-title":"J. Algorithms"},{"key":"339_CR44","unstructured":"Shannon, C.: Presentation of a maze-solving machine. In: Proceedings of the 8th Conference of the Josiah Macy Jr. Foundation (Cybernetics), pp. 173\u2013180 (1951)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-0339-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-018-0339-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-0339-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T12:59:22Z","timestamp":1693832362000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-018-0339-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,20]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["339"],"URL":"https:\/\/doi.org\/10.1007\/s00446-018-0339-1","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,20]]},"assertion":[{"value":"31 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}