{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T14:55:32Z","timestamp":1762786532356,"version":"build-2065373602"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T00:00:00Z","timestamp":1750723200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T00:00:00Z","timestamp":1750723200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery Grant 2017-05936","Discovery Grant 2018-03899"],"award-info":[{"award-number":["Discovery Grant 2017-05936","Discovery Grant 2018-03899"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00446-025-00489-5","type":"journal-article","created":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T22:17:09Z","timestamp":1750717029000},"page":"435-489","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast deterministic rendezvous in labeled lines"],"prefix":"10.1007","volume":"38","author":[{"given":"Avery","family":"Miller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,24]]},"reference":[{"key":"489_CR1","doi-asserted-by":"publisher","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000). https:\/\/doi.org\/10.1137\/1.9780898719772","DOI":"10.1137\/1.9780898719772"},{"key":"489_CR2","doi-asserted-by":"publisher","unstructured":"Collins, A., Czyzowicz, J., Gasieniec, L., Kosowski, A., Martin, R.A.: Synchronous rendezvous for location-aware agents. In: Peleg, D. (ed.) Distributed Computing - 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6950, pp. 447\u2013459. Springer, Berlin, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-24100-0_42","DOI":"10.1007\/978-3-642-24100-0_42"},{"issue":"1","key":"489_CR3","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00453-006-0074-2","volume":"46","author":"A Dessmark","year":"2006","unstructured":"Dessmark, A., Fraigniaud, P., Kowalski, D.R., Pelc, A.: Deterministic rendezvous in graphs. Algorithmica 46(1), 69\u201396 (2006). https:\/\/doi.org\/10.1007\/s00453-006-0074-2","journal-title":"Algorithmica"},{"issue":"1","key":"489_CR4","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control. 70(1), 32\u201353 (1986). https:\/\/doi.org\/10.1016\/S0019-9958(86)80023-7","journal-title":"Inf. Control."},{"key":"489_CR5","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. International Series in Operations Research & Management Science, vol. 55. Springer, New York, NY (2003)"},{"issue":"3","key":"489_CR6","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1137\/S0363012993249195","volume":"33","author":"S Alpern","year":"1995","unstructured":"Alpern, S.: The rendezvous search problem. SIAM Journal on Control and Optimization 33(3), 673\u2013683 (1995). https:\/\/doi.org\/10.1137\/S0363012993249195","journal-title":"SIAM Journal on Control and Optimization"},{"issue":"3","key":"489_CR7","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1002\/nav.10011","volume":"49","author":"S Alpern","year":"2002","unstructured":"Alpern, S.: Rendezvous search on labeled networks. Naval Research Logistics (NRL) 49(3), 256\u2013274 (2002). https:\/\/doi.org\/10.1002\/nav.10011","journal-title":"Naval Research Logistics (NRL)"},{"key":"489_CR8","doi-asserted-by":"crossref","unstructured":"Anderson, E.J., Weber, R.R.: The rendezvous problem on discrete locations. Journal of Applied Probability 27(4), 839\u2013851 (1990). Accessed 2023-04-24","DOI":"10.1017\/S0021900200028011"},{"issue":"6","key":"489_CR9","doi-asserted-by":"publisher","first-page":"1880","DOI":"10.1137\/S0363012996314130","volume":"36","author":"V Baston","year":"1998","unstructured":"Baston, V., Gal, S.: Rendezvous on the line when the players\u2019 initial distance is given by an unknown probability distribution. SIAM Journal on Control and Optimization 36(6), 1880\u20131889 (1998). https:\/\/doi.org\/10.1137\/S0363012996314130","journal-title":"SIAM Journal on Control and Optimization"},{"issue":"3","key":"489_CR10","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/net.21453","volume":"59","author":"A Pelc","year":"2012","unstructured":"Pelc, A.: Deterministic rendezvous in networks: A comprehensive survey. Networks 59(3), 331\u2013347 (2012). https:\/\/doi.org\/10.1002\/net.21453","journal-title":"Networks"},{"key":"489_CR11","doi-asserted-by":"publisher","unstructured":"Pelc, A.: Deterministic rendezvous algorithms. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing. Lecture Notes in Computer Science, vol. 11340, pp. 423\u2013454. Springer, Cham, Switzerland (2019). https:\/\/doi.org\/10.1007\/978-3-030-11072-7_17","DOI":"10.1007\/978-3-030-11072-7_17"},{"issue":"8","key":"489_CR12","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1002\/nav.1044","volume":"48","author":"V Baston","year":"2001","unstructured":"Baston, V., Gal, S.: Rendezvous search when marks are left at the starting points. Naval Research Logistics 48(8), 722\u2013731 (2001). https:\/\/doi.org\/10.1002\/nav.1044","journal-title":"Naval Research Logistics"},{"key":"489_CR13","doi-asserted-by":"publisher","unstructured":"Anderson, E.J., Fekete, S.P.: Asymmetric rendezvous on the plane. In: Janardan, R. (ed.) Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Minneapolis, Minnesota, USA, June 7-10, 1998, pp. 365\u2013373. ACM, New York, NY (1998). https:\/\/doi.org\/10.1145\/276884.276925","DOI":"10.1145\/276884.276925"},{"issue":"1","key":"489_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1287\/opre.49.1.107.11191","volume":"49","author":"EJ Anderson","year":"2001","unstructured":"Anderson, E.J., Fekete, S.P.: Two dimensional rendezvous search. Oper. Res. 49(1), 107\u2013118 (2001). https:\/\/doi.org\/10.1287\/opre.49.1.107.11191","journal-title":"Oper. Res."},{"key":"489_CR15","doi-asserted-by":"publisher","unstructured":"Bouchard, S., Dieudonn\u00e9, Y., Pelc, A., Petit, F.: Almost universal anonymous rendezvous in the plane. In: Scheideler, C., Spear, M. (eds.) SPAA \u201920: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pp. 117\u2013127. ACM, New York, NY (2020). https:\/\/doi.org\/10.1145\/3350755.3400283","DOI":"10.1145\/3350755.3400283"},{"key":"489_CR16","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., Gasieniec, L., Killick, R., Kranakis, E.: Symmetry breaking in the plane: Rendezvous by robots with unknown attributes. In: Robinson, P., Ellen, F. (eds.) Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pp. 4\u201313. ACM, New York, NY (2019). https:\/\/doi.org\/10.1145\/3293611.3331608","DOI":"10.1145\/3293611.3331608"},{"issue":"1\u20133","key":"489_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2005.01.001","volume":"337","author":"P Flocchini","year":"2005","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1\u20133), 147\u2013168 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.01.001","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"489_CR18","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1137\/S036301299427816X","volume":"34","author":"WS Lim","year":"1996","unstructured":"Lim, W.S., Alpern, S.: Minimax rendezvous on the line. SIAM Journal on Control and Optimization 34(5), 1650\u20131665 (1996). https:\/\/doi.org\/10.1137\/S036301299427816X","journal-title":"SIAM Journal on Control and Optimization"},{"issue":"6","key":"489_CR19","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1057\/jors.1992.89","volume":"43","author":"LC Thomas","year":"1992","unstructured":"Thomas, L.C.: Finding your kids when they are lost. Journal of the Operational Research Society 43(6), 637\u2013639 (1992). https:\/\/doi.org\/10.1057\/jors.1992.89","journal-title":"Journal of the Operational Research Society"},{"issue":"6\u20137","key":"489_CR20","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1002\/nav.21818","volume":"65","author":"P Leone","year":"2018","unstructured":"Leone, P., Alpern, S.: Rendezvous search with markers that can be dropped at chosen times. Naval Research Logistics (NRL) 65(6\u20137), 449\u2013461 (2018). https:\/\/doi.org\/10.1002\/nav.21818","journal-title":"Naval Research Logistics (NRL)"},{"issue":"2","key":"489_CR21","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1016\/J.EJOR.2021.05.009","volume":"297","author":"P Leone","year":"2022","unstructured":"Leone, P., Buwaya, J., Alpern, S.: Search-and-rescue rendezvous. Eur. J. Oper. Res. 297(2), 579\u2013591 (2022). https:\/\/doi.org\/10.1016\/J.EJOR.2021.05.009","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"489_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.3390\/A15020041","volume":"15","author":"P Leone","year":"2022","unstructured":"Leone, P., Cohen, N.: Rendezvous on the line with different speeds and markers that can be dropped at chosen time. Algorithms 15(2), 41 (2022). https:\/\/doi.org\/10.3390\/A15020041","journal-title":"Algorithms"},{"key":"489_CR23","doi-asserted-by":"publisher","unstructured":"Kranakis, E., Santoro, N., Sawchuk, C., Krizanc, D.: Mobile agent rendezvous in a ring. In: 23rd International Conference on Distributed Computing Systems (ICDCS 2003), 19-22 May 2003, Providence, RI, USA, pp. 592\u2013599. IEEE Computer Society, USA (2003). https:\/\/doi.org\/10.1109\/ICDCS.2003.1203510","DOI":"10.1109\/ICDCS.2003.1203510"},{"issue":"1\u20132","key":"489_CR24","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.tcs.2008.02.010","volume":"399","author":"DR Kowalski","year":"2008","unstructured":"Kowalski, D.R., Malinowski, A.: How to meet in anonymous network. Theor. Comput. Sci. 399(1\u20132), 141\u2013156 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.02.010","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"489_CR25","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2601068","volume":"10","author":"A Ta-Shma","year":"2014","unstructured":"Ta-Shma, A., Zwick, U.: Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Trans. Algorithms 10(3), 12\u201311215 (2014). https:\/\/doi.org\/10.1145\/2601068","journal-title":"ACM Trans. Algorithms"},{"key":"489_CR26","doi-asserted-by":"publisher","unstructured":"Bhagat, S., Pelc, A.: Deterministic rendezvous in infinite trees. CoRR abs\/2203.05160 (2022) https:\/\/doi.org\/10.48550\/arXiv.2203.05160","DOI":"10.48550\/arXiv.2203.05160"},{"key":"489_CR27","doi-asserted-by":"publisher","unstructured":"Bhagat, S., Pelc, A.: How to meet at a node of any connected graph. In: Scheideler, C. (ed.) 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA. LIPIcs, vol. 246, pp. 11\u201311116. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2022.11","DOI":"10.4230\/LIPIcs.DISC.2022.11"},{"issue":"2","key":"489_CR28","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1007\/s00453-015-9982-0","volume":"74","author":"Y Dieudonn\u00e9","year":"2016","unstructured":"Dieudonn\u00e9, Y., Pelc, A.: Anonymous meeting in networks. Algorithmica 74(2), 908\u2013946 (2016). https:\/\/doi.org\/10.1007\/s00453-015-9982-0","journal-title":"Algorithmica"},{"key":"489_CR29","doi-asserted-by":"publisher","unstructured":"Miller, A., Pelc, A.: Tradeoffs between cost and information for rendezvous and treasure hunt. J. Parallel Distributed Comput. 83, 159\u2013167 (2015) https:\/\/doi.org\/10.1016\/j.jpdc.2015.06.004","DOI":"10.1016\/j.jpdc.2015.06.004"},{"key":"489_CR30","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Pelc, A.: Delays induce an exponential memory gap for rendezvous in trees. ACM Trans. Algorithms 9(2), 17\u201311724 (2013). https:\/\/doi.org\/10.1145\/2438645.2438649","DOI":"10.1145\/2438645.2438649"},{"issue":"2","key":"489_CR31","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00446-011-0141-9","volume":"25","author":"J Czyzowicz","year":"2012","unstructured":"Czyzowicz, J., Kosowski, A., Pelc, A.: How to meet when you forget: log-space rendezvous in arbitrary graphs. Distributed Comput. 25(2), 165\u2013178 (2012). https:\/\/doi.org\/10.1007\/s00446-011-0141-9","journal-title":"Distributed Comput."},{"issue":"3","key":"489_CR32","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/1978782.1978789","volume":"7","author":"E Kranakis","year":"2011","unstructured":"Kranakis, E., Krizanc, D., Morin, P.: Randomized rendezvous with limited memory. ACM Trans. Algorithms 7(3), 34\u201313412 (2011). https:\/\/doi.org\/10.1145\/1978782.1978789","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"489_CR33","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/S00446-018-0338-2","volume":"32","author":"S Bouchard","year":"2019","unstructured":"Bouchard, S., Bournat, M., Dieudonn\u00e9, Y., Dubois, S., Petit, F.: Asynchronous approach in the plane: a deterministic polynomial algorithm. Distributed Comput. 32(4), 317\u2013337 (2019). https:\/\/doi.org\/10.1007\/S00446-018-0338-2","journal-title":"Distributed Comput."},{"issue":"4","key":"489_CR34","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1137\/100796534","volume":"41","author":"M Cieliebak","year":"2012","unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: Gathering. SIAM J. Comput. 41(4), 829\u2013879 (2012). https:\/\/doi.org\/10.1137\/100796534","journal-title":"SIAM J. Comput."},{"key":"489_CR35","doi-asserted-by":"publisher","unstructured":"Bampas, E., Czyzowicz, J., Gasieniec, L., Ilcinkas, D., Labourel, A.: Almost optimal asynchronous rendezvous in infinite multidimensional grids. In: Lynch, N.A., Shvartsman, A.A. (eds.) Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6343, pp. 297\u2013311. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15763-9_28","DOI":"10.1007\/978-3-642-15763-9_28"},{"issue":"3","key":"489_CR36","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1137\/130931990","volume":"44","author":"Y Dieudonn\u00e9","year":"2015","unstructured":"Dieudonn\u00e9, Y., Pelc, A., Villain, V.: How to meet asynchronously at polynomial cost. SIAM J. Comput. 44(3), 844\u2013867 (2015). https:\/\/doi.org\/10.1137\/130931990","journal-title":"SIAM J. Comput."},{"issue":"3","key":"489_CR37","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/J.TCS.2005.12.016","volume":"355","author":"GD Marco","year":"2006","unstructured":"Marco, G.D., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. Theor. Comput. Sci. 355(3), 315\u2013326 (2006). https:\/\/doi.org\/10.1016\/J.TCS.2005.12.016","journal-title":"Theor. Comput. Sci."},{"key":"489_CR38","doi-asserted-by":"publisher","unstructured":"Bourreau, Y., Narayanan, A., Nolin, A.: Optimal deterministic rendezvous in labeled lines. CoRR abs\/2505.04564 (2025) https:\/\/doi.org\/10.48550\/arXiv.2505.04564","DOI":"10.48550\/arXiv.2505.04564"},{"key":"489_CR39","unstructured":"Laurinharju, J., Suomela, J.: Linial\u2019s lower bound made easy. CoRR abs\/1402.2552 (2014)"},{"issue":"1","key":"489_CR40","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing 21(1), 193\u2013201 (1992). https:\/\/doi.org\/10.1137\/0221015","journal-title":"SIAM Journal on Computing"},{"key":"489_CR41","unstructured":"Wattenhofer, R.: Principles of distributed computing. Accessed on 2023-04-16 (2023). https:\/\/disco.ethz.ch\/courses\/fs23\/podc\/ Accessed 2023-04-16"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00489-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00489-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00489-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T14:53:49Z","timestamp":1762786429000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00489-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,24]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["489"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00489-5","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,6,24]]},"assertion":[{"value":"30 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}