Optimal graph exploration without good maps

DOI10.1016/j.tcs.2004.07.031zbMath1071.68081OpenAlexW1980155648MaRDI QIDQ703557

Anders Dessmark, Andrzej Pelc

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.07.031

zbMATH Keywords

exploration algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Artificial intelligence for robotics (68T40)

Related Items (24)

Fault-tolerant sequential scan ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ The ANTS problem ⋮ Online graph exploration: New results on old and new algorithms ⋮ Grid exploration by a swarm of autonomous robots with minimum repetitions ⋮ Impact of knowledge on the cost of treasure hunt in trees ⋮ Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots ⋮ On the Power of Local Orientations ⋮ Exploration of carrier-based time-varying networks: the power of waiting ⋮ Drawing maps with advice ⋮ Exploration of Faulty Hamiltonian Graphs ⋮ Deterministic network exploration by a single agent with Byzantine tokens ⋮ Map construction of unknown graphs by multiple agents ⋮ Online Graph Exploration: New Results on Old and New Algorithms ⋮ Tree exploration with advice ⋮ Remembering without memory: tree exploration by asynchronous oblivious robots ⋮ Trade-offs between the size of advice and broadcasting time in trees ⋮ Communication algorithms with advice ⋮ Deterministic Models of Communication Faults ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Fast collaborative graph exploration ⋮ Distributed graph searching with a sense of direction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to learn an unknown environment. I
• Online Navigation in a Room
• Navigating in Unfamiliar Geometric Terrain
• Impact of topographic information on graph exploration efficiency
• Exploring an unknown graph
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments

This page was built for publication: Optimal graph exploration without good maps