A tight lower bound for semi-synchronous collaborative grid exploration

DOI10.1007/S00446-020-00369-0zbMATH Open1462.68009OpenAlexW3003210445MaRDI QIDQ2220396FDOQ2220396

Authors: Jara Uitto, Roger Wattenhofer, Sebastian F. Brandt 

Publication date: 22 January 2021

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-020-00369-0

Recommendations

• A tight lower bound for semi-synchronous collaborative grid exploration
• On the minimum universal collectives of automata for plane labyrinths
• Exploring an infinite space with finite memory scouts
• scientific article; zbMATH DE number 2036576
• A general lower bound for collaborative tree exploration

zbMATH Keywords

finite automatamobile robotsgraph explorationagents

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Searching in the plane
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Exploring an unknown graph
• Title not available (Why is that?)
• Collaborative search on the plane without communication
• Tree exploration with little memory
• Exploring Unknown Environments
• Solving the ANTS problem with asynchronous finite state machines
• STACS 2004
• Automata and Labyrinths
• Optimal constrained graph exploration
• Group search on the line
• Title not available (Why is that?)
• How many ants does it take to find the food?
• Title not available (Why is that?)
• Exploring an infinite space with finite memory scouts
• Title not available (Why is that?)
• Undirected Graph Exploration with ⊝(log log n) Pebbles

Cited In (5)

• A general lower bound for collaborative tree exploration
• A tight lower bound for semi-synchronous collaborative grid exploration
• Tight bounds for deterministic high-dimensional grid exploration
• Title not available (Why is that?)
• Exploring an infinite space with finite memory scouts

This page was built for publication: A tight lower bound for semi-synchronous collaborative grid exploration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220396)