Premium
Collective tree exploration
Author(s) -
Fraigniaud Pierre,
Ga̧sieniec Leszek,
Kowalski Dariusz R.,
Pelc Andrzej
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20127
Subject(s) - computer science , tree (set theory) , node (physics) , robot , search tree , scheduling (production processes) , enhanced data rates for gsm evolution , theoretical computer science , artificial intelligence , algorithm , mathematical optimization , mathematics , combinatorics , search algorithm , engineering , structural engineering
An n ‐node tree has to be explored by k mobile agents (robots), starting at its root. Every edge of the tree must be traversed by at least one robot, and exploration must be completed as fast as possible. Even when the tree is known in advance, scheduling optimal collective exploration turns out to be NP‐hard. We investigate the problem of how communication among robots influences the time for exploring unknown trees. To this end, we consider two scenarios. In the first scenario, robots can communicate by writing at the currently visited node previously acquired information, and reading information available at this node. In the second scenario robots are oblivious of one another, and each of them knows only the part of the tree previously explored by itself. We show that this difference of communication capability significantly influences time of collective exploration. Under the first scenario, we construct an exploration algorithm whose running time for any tree is only O ( k / log k ) larger than the optimal exploration time with full knowledge of the tree, while under the second scenario we prove that every algorithm works in time Ω ( k ) larger than optimal, for some trees. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(3), 166–177 2006