Delays Induce an Exponential Memory Gap for Rendezvous in Trees

DOI10.1145/2438645.2438649zbMath1301.68203arXiv1102.0467OpenAlexW2081055073MaRDI QIDQ2933647

Andrzej Pelc, Pierre Fraigniaud

Publication date: 5 December 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.0467

zbMATH Keywords

rendezvousexplorationcompact data structure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Agent technology and artificial intelligence (68T42)

Related Items (22)

Byzantine gathering in networks ⋮ Rendezvous in networks in spite of delay faults ⋮ Byzantine gathering in polynomial time ⋮ Move-optimal partial gathering of mobile agents in asynchronous trees ⋮ Almost universal anonymous rendezvous in the plane ⋮ Fast rendezvous with advice ⋮ How to meet when you forget: log-space rendezvous in arbitrary graphs ⋮ Deterministic rendezvous in infinite trees ⋮ Unnamed Item ⋮ Byzantine Gathering in Networks with Authenticated Whiteboards ⋮ How much memory is needed for leader election ⋮ Use of information, memory and randomization in asynchronous gathering ⋮ Time versus space trade-offs for rendezvous in trees ⋮ How to meet asynchronously at polynomial cost ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Deterministic Rendezvous with Detection Using Beeps ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Asynchronous approach in the plane: a deterministic polynomial algorithm ⋮ Deterministic Meeting of Sniffing Agents in the Plane ⋮ Unnamed Item ⋮ Deterministic polynomial approach in the plane ⋮ Anonymous meeting in networks

This page was built for publication: Delays Induce an Exponential Memory Gap for Rendezvous in Trees