Tree exploration with little memory

DOI10.1016/j.jalgor.2003.10.002zbMath1067.68100OpenAlexW2017617294MaRDI QIDQ4818671

Andrzej Pelc, Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis

Publication date: 1 October 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2003.10.002

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Artificial intelligence for robotics (68T40)

Related Items (35)

Memory optimal dispersion by anonymous mobile robots ⋮ OPTIMAL CONSTRUCTION OF SENSE OF DIRECTION IN A TORUS BY A MOBILE AGENT ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Collaborative Exploration by Energy-Constrained Mobile Robots ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ A nearly optimal randomized algorithm for explorable heap selection ⋮ How many ants does it take to find the food? ⋮ How to meet when you forget: log-space rendezvous in arbitrary graphs ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Graph covering using bounded size subgraphs ⋮ Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles ⋮ IMPLEMENTATION OF GRAPH THEORY AND APPLICATION BY MAXIMA SOFTWARE ⋮ Exploration of Faulty Hamiltonian Graphs ⋮ Deterministic network exploration by a single agent with Byzantine tokens ⋮ Searching for a black hole in arbitrary networks: optimal mobile agents protocols ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Building a nest by an automaton ⋮ Fast periodic graph exploration with constant memory ⋮ Map construction of unknown graphs by multiple agents ⋮ Setting port numbers for fast graph exploration ⋮ Memory optimal dispersion by anonymous mobile robots ⋮ LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS ⋮ Impact of memory size on graph exploration capability ⋮ Tree exploration with advice ⋮ Unnamed Item ⋮ Weighted nearest neighbor algorithms for the graph exploration problem on cycles ⋮ Collaborative exploration of trees by energy-constrained mobile robots ⋮ A general lower bound for collaborative tree exploration ⋮ Self-stabilizing robots in highly dynamic environments ⋮ Connected reconfiguration of lattice-based cellular structures by finite-memory robots ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Graph exploration by a finite automaton ⋮ Exploring sparse graphs with advice

This page was built for publication: Tree exploration with little memory