2026-07-26T00:23:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19563 2024-03-06T11:04:20Z ddc:004 open_access

Collective Tree Exploration via Potential Function Method Cosson, Romain Massoulié, Laurent collective exploration online algorithms evolving tree competitive analysis We study the problem of collective tree exploration (CTE) in which a team of k agents is tasked to traverse all the edges of an unknown tree as fast as possible, assuming complete communication between the agents [FGKP06]. In this paper, we present an algorithm performing collective tree exploration in 2n/k+𝒪(kD) rounds, where n is the number of nodes in the tree, and D is the tree depth. This leads to a competitive ratio of 𝒪(√k), the first polynomial improvement over the 𝒪(k) ratio of depth-first search. Our analysis holds for an asynchronous generalization of collective tree exploration. It relies on a game with robots at the leaves of a continuously growing tree extending the "tree-mining game" of [C23] and resembling the "evolving tree game" of [BCR22]. Another surprising consequence of our results is the existence of algorithms {𝒜_k}_{k ∈ ℕ} for layered tree traversal (LTT) with cost at most 2L/k+𝒪(kD), where L is the sum of all edge lengths. For the case of layered trees of width w and unit edge lengths, our guarantee is thus in 𝒪(√wD). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Romain Cosson and Laurent Massoulié 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.35 urn:nbn:de:0030-drops-195638 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode