Tree exploration with logarithmic memory
From MaRDI portal
Publication:3188999
DOI10.1145/1921659.1921663zbMath1295.68203MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W15: Distributed algorithms
Related Items
Unnamed Item, Energy-Optimal Broadcast in a Tree with Mobile Agents, Exploration of Time-Varying Connected Graphs with Silent Agents, 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, Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles, Deterministic network exploration by a single agent with Byzantine tokens, Computing on rings by oblivious robots: a unified approach for different tasks, Derandomizing random walks in undirected graphs using locally fair exploration strategies, Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers, On mobile agent verifiable problems, Leader election for anonymous asynchronous agents in arbitrary networks, Energy-optimal broadcast and exploration in a tree using mobile agents, Distributed graph searching with a sense of direction, 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
