Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Spanner planaire pour le Unit Disk Graph
du 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