Tree exploration with logarithmic memory

DOI10.1145/1921659.1921663zbMath1295.68203OpenAlexW2152623377MaRDI QIDQ3188999

Xiaohui Zhang, Andrzej Pelc, Tomasz Radzik, Leszek Gąsieniec, Christoph Ambühl

Publication date: 9 September 2014

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

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

zbMATH Keywords

distributed algorithmsgraph explorationsmall memory

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (19)

Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers ⋮ Energy-Optimal Broadcast in a Tree with Mobile Agents ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ The ANTS problem ⋮ Searching without communicating: tradeoffs between performance and selection complexity ⋮ Robustness of the rotor-router mechanism ⋮ Exploration of Time-Varying Connected Graphs with Silent Agents ⋮ Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles ⋮ Unnamed Item ⋮ Deterministic network exploration by a single agent with Byzantine tokens ⋮ Derandomizing random walks in undirected graphs using locally fair exploration strategies ⋮ Computing on rings by oblivious robots: a unified approach for different tasks ⋮ On mobile agent verifiable problems ⋮ Leader election for anonymous asynchronous agents in arbitrary networks ⋮ A general lower bound for collaborative tree exploration ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Connected reconfiguration of lattice-based cellular structures by finite-memory robots ⋮ Energy-optimal broadcast and exploration in a tree using mobile agents ⋮ Distributed graph searching with a sense of direction

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