Evènement pour le groupe Algorithmique Distribuée


Date 2012-04-02  14:00-15:00
TitreSpanner planaire pour le Unit Disk Graph  
RésuméNous nous intéressons à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. De nombreux résultats existent pour les spanners en terme de distance Euclidienne de UDG, nous présentons ici un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Par rapport aux constructions précédemment proposées pour ce problème, nous assurons un facteur d'étirement significativement plus petit ainsi que la planarité totale du graphe. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée. Intervenant: Nicolas Catusse 
Lieus. 076 
OrateurNicolas Catusse 
Emailnicolas.catusse@lif.univ-mrs.fr 
UrlLIF - Univ. Marseille 



Aucun document lié à cet événement.

Retour
Retour à l'index