A general lower bound for collaborative tree exploration

DOI10.1016/j.tcs.2018.03.006zbMath1437.68205arXiv1610.01753OpenAlexW2789516566MaRDI QIDQ5919423

Nemanja Škorić, Yann Disser, Angelika Steger, Frank Mousset, Andreas Noever

Publication date: 13 February 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.01753

zbMATH Keywords

competitive analysislower boundsautonomous robotscollaborative graph exploration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Artificial intelligence for robotics (68T40) Online algorithms; streaming algorithms (68W27)

Related Items (2)

An improved lower bound for competitive graph exploration ⋮ Guarding a Polygon Without Losing Touch

Cites Work

• Unnamed Item
• Tight bounds for the cover time of multiple random walks
• Strategies for parallel unaware cleaners
• Piecemeal graph exploration by a mobile robot.
• The power of a pebble: Exploring and mapping directed graphs
• Mapping simple polygons: how robots benefit from looking back
• Online graph exploration algorithms for cycles and trees by multiple searchers
• Fast collaborative graph exploration
• Graph exploration by a finite automaton
• Optimal constrained graph exploration
• Tree exploration with logarithmic memory
• Collective tree exploration
• Undirected connectivity in log-space
• Undirected Graph Exploration with ⊝(log log n) Pebbles
• Exploring an unknown graph
• Tree exploration with little memory
• Exploring Unknown Environments
• Mapping Simple Polygons
• Many Random Walks Are Faster Than One
• Why Robots Need Maps
• A Recursive Approach to Multi-robot Exploration of Trees

This page was built for publication: A general lower bound for collaborative tree exploration