Brief Announcement: Distributed Exclusive and Perpetual Tree Searching - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

## Brief Announcement: Distributed Exclusive and Perpetual Tree Searching

(1, 2) , (3, 4) , (5)
1
2
3
4
5
Lélia Blin
Janna Burman
Nicolas Nisse

#### Abstract

We tackle a practical version of the well known {\it graph searching} problem, where a team of robots aims at capturing an intruder in a graph. The robots and the intruder move along the edges of the graph. The intruder is invisible, arbitrary fast, and omniscient. It is caught whenever it stands on a node occupied by a robot, and cannot escape to a neighboring node. We study graph searching in the CORDA model of mobile computing: robots are asynchronous, and they perform cycles of {\it Look-Compute-Move} actions. Moreover, motivated by physical constraints, we consider the \emph{exclusive} property, stating that no two or more robots can occupy the same node at the same time. In addition, we assume that the network and the robots are anonymous. Finally, robots are \emph{oblivious}, i.e., each robot performs its move actions based only on its current ''vision'' of the positions of the other robots. Our objective is to characterize, for a graph $G$, the set of integers $k$ such that graph searching can be achieved by a team of $k$ robots starting from \emph{any} $k$ distinct nodes in $G$. Our main result consists in a full characterization of this set, for any asymmetric tree. Towards providing a characterization for all trees, including trees with non-trivial automorphisms, we have also provides a set of positive and negative results, including a full characterization for any line. All our positive results are based on the design of algorithms enabling \emph{perpetual} graph searching to be achieved with the desired number of robots.

### Dates and versions

hal-00741982 , version 1 (15-10-2012)

### Identifiers

• HAL Id : hal-00741982 , version 1
• DOI :

### Cite

Lélia Blin, Janna Burman, Nicolas Nisse. Brief Announcement: Distributed Exclusive and Perpetual Tree Searching. DISC 2012 - 26th International Symposium on Distributed Computing, Oct 2012, Salvador, Brazil. pp.403-404, ⟨10.1007/978-3-642-33651-5_29⟩. ⟨hal-00741982⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

532 View