Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences

DOI10.1145/2601068zbMath1333.68216OpenAlexW2114858735WikidataQ62398446 ScholiaQ62398446MaRDI QIDQ2799477

Uri Zwick, Amnon Ta-Shma

Publication date: 11 April 2016

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

Full work available at URL: https://doi.org/10.1145/2601068

zbMATH Keywords

rendezvousmobile robotsuniversal traversal sequencestreasure huntuniversal exploration sequences

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Artificial intelligence for robotics (68T40) Agent technology and artificial intelligence (68T42)

Related Items (29)

Byzantine gathering in networks ⋮ Memory optimal dispersion by anonymous mobile robots ⋮ Unnamed Item ⋮ Byzantine gathering in polynomial time ⋮ Treasure Hunt with Advice ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Pebble guided optimal treasure hunt in anonymous graphs ⋮ Almost universal anonymous rendezvous in the plane ⋮ Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs ⋮ Impact of knowledge on the cost of treasure hunt in trees ⋮ Deterministic rendezvous in infinite trees ⋮ Unnamed Item ⋮ On deterministic rendezvous at a node of agents with arbitrary velocities ⋮ Deterministic treasure hunt in the plane with angular hints ⋮ Different Speeds Suffice for Rendezvous of Two Agents on Arbitrary Graphs ⋮ Byzantine Gathering in Networks with Authenticated Whiteboards ⋮ Memory optimal dispersion by anonymous mobile robots ⋮ How to meet asynchronously at polynomial cost ⋮ Unnamed Item ⋮ Gathering in dynamic rings ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Reaching a target in the plane with no information ⋮ Connected reconfiguration of lattice-based cellular structures by finite-memory robots ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Asynchronous approach in the plane: a deterministic polynomial algorithm ⋮ Deterministic Meeting of Sniffing Agents in the Plane ⋮ Pebble guided near optimal treasure hunt in anonymous graphs ⋮ Anonymous meeting in networks

Cites Work

• Unnamed Item
• How to meet in anonymous network
• Meeting times for independent Markov chains
• Universal traversal sequences with backtracking.
• Asynchronous deterministic rendezvous in graphs
• Deterministic rendezvous in graphs
• Collisions Among Random Walks on a Graph
• Undirected connectivity in log-space
• Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
• Algorithms and Computation
• Algorithms - ESA 2003

This page was built for publication: Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences