{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:02Z","timestamp":1750307402995,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,13]],"date-time":"2010-06-13T00:00:00Z","timestamp":1276387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,6,13]]},"DOI":"10.1145\/1810479.1810524","type":"proceedings-article","created":{"date-parts":[[2010,6,15]],"date-time":"2010-06-15T13:11:04Z","timestamp":1276607464000},"page":"224-232","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Delays induce an exponential memory gap for rendezvous in trees"],"prefix":"10.1145","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[{"name":"CNRS and Univ. Paris Diderot, Paris, France"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Canada"}]}],"member":"320","published-online":{"date-parts":[[2010,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993249195"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10011"},{"key":"e_1_3_2_1_3_1","volume-title":"Int. Series in Operations research and Management Science","author":"Alpern S.","year":"2002","unstructured":"S. Alpern and S. Gal , The theory of search games and rendezvous . Int. Series in Operations research and Management Science , Kluwer Academic Publisher , 2002 . S. Alpern and S. Gal, The theory of search games and rendezvous. Int. Series in Operations research and Management Science,Kluwer Academic Publisher, 2002."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1032374243"},{"key":"e_1_3_2_1_5_1","first-page":"839","volume":"28","author":"Anderson E.","year":"1990","unstructured":"E. Anderson and R. Weber , The rendezvous problem on discrete locations, Journal of Applied Probability 28 ( 1990 ), 839 -- 851 . E. Anderson and R. Weber, The rendezvous problem on discrete locations, Journal of Applied Probability 28 (1990), 839--851.","journal-title":"The rendezvous problem on discrete locations, Journal of Applied Probability"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276925"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.1.107.11191"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012996314130"},{"key":"e_1_3_2_1_9_1","volume-title":"Naval Reaserch Logistics 48","author":"Baston V.","year":"2001","unstructured":"V. Baston and S. Gal , Rendezvous search when marks are left at the startingpoints , Naval Reaserch Logistics 48 ( 2001 ), 722--731. V. Baston and S. Gal,Rendezvous search when marks are left at the startingpoints, Naval Reaserch Logistics 48 (2001), 722--731."},{"key":"e_1_3_2_1_10_1","volume-title":"Space Lower Bounds for Maze Threadability on Restricted Machines.SIAM J. Comput. 9","author":"Cook S. A.","year":"1980","unstructured":"S. A. Cook and C. Rackoff . Space Lower Bounds for Maze Threadability on Restricted Machines.SIAM J. Comput. 9 ( 1980 ), 636--652. S. A. Cook and C. Rackoff. Space Lower Bounds for Maze Threadability on Restricted Machines.SIAM J. Comput. 9 (1980), 636--652."},{"key":"e_1_3_2_1_11_1","volume-title":"Introduction to Algorithms","author":"Cormen T.H.","year":"1990","unstructured":"T.H. Cormen , C.E. Leiserson , R.L. Rivest , Introduction to Algorithms , McGraw-Hill 1990 . T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill 1990."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.016"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118736.3118835"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.002"},{"key":"e_1_3_2_1_15_1","volume-title":"18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001","author":"Flocchini P.","year":"2010","unstructured":"P. Flocchini , G. Prencipe , N. Santoro , P. Widmayer ,Gathering of asynchronous oblivious robots with limited visibility,Proc . 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001 ),LNCS 2010 , 247--258. P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer,Gathering of asynchronous oblivious robots with limited visibility,Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001),LNCS 2010, 247--258."},{"key":"e_1_3_2_1_16_1","volume-title":"A Space Lower Bound for Routing in Trees.In 19th Annual Symp. on Theoretical Aspects of Computer Science (STACS","author":"Fraigniaud P.","year":"2002","unstructured":"P. Fraigniaud and C. Gavoille . A Space Lower Bound for Routing in Trees.In 19th Annual Symp. on Theoretical Aspects of Computer Science (STACS 2002 ), Springer LNCS 2285, 65--75. P. Fraigniaud and C. Gavoille.A Space Lower Bound for Routing in Trees.In 19th Annual Symp. on Theoretical Aspects of Computer Science (STACS 2002), Springer LNCS 2285, 65--75."},{"key":"e_1_3_2_1_17_1","volume-title":"28th Int. Colloquium on Automata, Languages and Programming (ICALP","author":"Fraigniaud P.","year":"2001","unstructured":"P. Fraigniaud and C. Gavoille . Routing in Trees . In 28th Int. Colloquium on Automata, Languages and Programming (ICALP 2001 ), Springer LNCS 2076, 757--772. P. Fraigniaud and C. Gavoille. Routing in Trees. In 28th Int. Colloquium on Automata, Languages and Programming (ICALP 2001), Springer LNCS 2076, 757--772."},{"key":"e_1_3_2_1_18_1","volume-title":"Digraphs Exploration with Little Memory. 21st Symp. on Theoretical Aspects of Comp. Science (STACS","author":"Fraigniaud P.","year":"2004","unstructured":"P. Fraigniaud and D. Ilcinkas . Digraphs Exploration with Little Memory. 21st Symp. on Theoretical Aspects of Comp. Science (STACS 2004 ), Springer LNCS 2996, 246--257. P. Fraigniaud and D. Ilcinkas. Digraphs Exploration with Little Memory. 21st Symp. on Theoretical Aspects of Comp. Science (STACS 2004), Springer LNCS 2996, 246--257."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_17"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.6.974"},{"key":"e_1_3_2_1_21_1","volume-title":"Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Gasieniec L.","year":"2007","unstructured":"L. Gasieniec , A. Pelc , T. Radzik , X. Zhang, Tree exploration with logarithmic memory , Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007 ), 585--594. L. Gasieniec, A. Pelc, T. Radzik, X. Zhang, Tree exploration with logarithmic memory, Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 585--594."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93409"},{"key":"e_1_3_2_1_23_1","volume-title":"Proc. 16th IEEE Conference on Computational Complexity","author":"Kouck\u1ef3 M.","year":"2001","unstructured":"M. Kouck\u1ef3 , Universal Traversal Sequences with Backtracking , Proc. 16th IEEE Conference on Computational Complexity ( 2001 ), 21--26. (Also, to appear in J. Computer and System Sciences.) M. Kouck\u1ef3, Universal Traversal Sequences with Backtracking, Proc. 16th IEEE Conference on Computational Complexity (2001), 21--26. (Also, to appear in J. Computer and System Sciences.)"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780823_5"},{"key":"e_1_3_2_1_25_1","volume-title":"8th Latin American Theoretical Informatics (LATIN","author":"Kranakis E.","year":"2008","unstructured":"E. Kranakis , D. Krizanc , and P. Morin , Randomized Rendez-Vous with Limited Memory,Proc . 8th Latin American Theoretical Informatics (LATIN 2008 ), Springer LNCS 4957, 605--616. E. Kranakis, D. Krizanc, and P. Morin, Randomized Rendez-Vous with Limited Memory,Proc. 8th Latin American Theoretical Informatics (LATIN 2008), Springer LNCS 4957, 605--616."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/850929.851981"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/235049.235058"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_3_2_1_29_1","volume-title":"Oxford","author":"Schelling T.","year":"1960","unstructured":"T. Schelling ,The strategy of conflict,Oxford University Press , Oxford , 1960 . T. Schelling,The strategy of conflict,Oxford University Press, Oxford, 1960."},{"key":"e_1_3_2_1_30_1","volume-title":"18th ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Ta-Shma A.","year":"2007","unstructured":"A. Ta-Shma and U. Zwick . Deterministic rendezvous, treasure hunts and strongly universal exploration sequences.Proc . 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007 ), 599--608. A. Ta-Shma and U. Zwick.Deterministic rendezvous, treasure hunts and strongly universal exploration sequences.Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 599--608."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1992.89"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/646250.685518"}],"event":{"name":"SPAA 10: 22nd ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture"],"location":"Thira Santorini Greece","acronym":"SPAA 10"},"container-title":["Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1810479.1810524","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1810479.1810524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:24Z","timestamp":1750246764000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1810479.1810524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,13]]},"references-count":32,"alternative-id":["10.1145\/1810479.1810524","10.1145\/1810479"],"URL":"https:\/\/doi.org\/10.1145\/1810479.1810524","relation":{},"subject":[],"published":{"date-parts":[[2010,6,13]]},"assertion":[{"value":"2010-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}