Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s)
Distributed Exclusive Graph Searching in Trees
Janna Burman

29 March 2013, 10h30 - 29 March 2013, 11h30
Salle/Bat : 475/PCRI-N
Contact :

Activités de recherche :

Résumé :
We consider a version of the well known graph searching problem, where a team of robots aims at clearing the contaminated edges of a graph.
We study graph searching in the model of mobile computing where
autonomous deterministic robots move between the graph nodes when
operating in asynchronous cycles of Look-Compute-Move. Moreover,
motivated by physical constraints, following some recent works, we
consider the exclusivity property, stating that no two or more robots
can occupy a same node at the same time. In addition, we assume that all
the graph elements and the robots are anonymous. Robots are oblivious
and have no sense of direction.


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 any $k$ distinct nodes in $G$. Our main result consists in a full characterization for any asymmetric tree. Towards providing a characterization in the general case, including trees with non-trivial automorphisms, we provide 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 perpetual graph searching to be achieved with the desired number of robots. We prove that, in addition to the distributed nature of our setting, the exclusivity property has a significant impact on the nature of the graph searching problem. Hence, the design of the algorithms requires to invent new methods.

Pour en savoir plus : http://tx.technion.ac.il/~bjanna/
Séminaires
A Two-level Auction for Resource Allocation in Mul
Réseaux sans fil et mobiles
Friday 09 March 2018 - 14h30
Salle : 445 - PCRI-N
Mira Morcos .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 09 February 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Approximate Bayesian Computation and Random Forest
Thursday 08 February 2018 - 00h00
Salle : 455 - PCRI-N
Valentin Thouzeau .............................................

A concurrent lock-free algorithm for computing a f
Combinatoire
Friday 12 January 2018 - 14h30
Salle : 445 - PCRI-N
James Mitchell .............................................

Acyclic Partitioning of Large Directed Acyclic Gra
Calcul à haute performance
Tuesday 09 January 2018 - 10h30
Salle : 465 - PCRI-N
Julien Herrmann .............................................