Label-guided graph exploration by a finite automaton

DOI10.1145/1383369.1383373zbMath1445.68157OpenAlexW2147342018MaRDI QIDQ4962747

David Ilcinkas, Reuven Cohen, Pierre Fraigniaud, Amos Korman, David Peleg

Publication date: 5 November 2018

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

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

zbMATH Keywords

distributed algorithmsgraph explorationlabeling schemes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (18)

Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots ⋮ Memory optimal dispersion by anonymous mobile robots ⋮ Byzantine gathering in polynomial time ⋮ Finding the size and the diameter of a radio network using short labels ⋮ Fast rendezvous with advice ⋮ Zero-memory graph exploration with unknown inports ⋮ Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles ⋮ Unnamed Item ⋮ Fault-tolerant dispersion of mobile robots ⋮ Lower and upper bounds for deterministic convergecast with labeling schemes ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Memory optimal dispersion by anonymous mobile robots ⋮ Computing on rings by oblivious robots: a unified approach for different tasks ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Dispersion of mobile robots on directed anonymous graphs ⋮ Topology recognition with advice ⋮ Pebble guided near optimal treasure hunt in anonymous graphs

This page was built for publication: Label-guided graph exploration by a finite automaton