Breadth-First Depth-Next: Optimal Collaborative Exploration of Trees with Low Diameter

Romain Cosson, Laurent Massoulié, Laurent Viennot

We consider the problem of collaborative tree exploration posed by Fraigniaud, Gasieniec, Kowalski, and Pelc where a team of $k$ agents is tasked to collectively go through all the…