Evènement pour le groupe Algorithmique Distribuée


Date 2009-06-29  14:00-15:00
TitreComputing Geometric Spanners Locally 
RésuméIn this talk, I will discuss a project to develop efficient local distributed algorithms for wireless communication by exploiting the geometry of wireless systems. A wireless system is often modeled as a graph in the Euclidean space -- such as the Unit Disk Graph (UDG) -- and geometric techniques are used to obtain insights about the structure of such graphs. So far, we obtained insights that have led us to the development of the currently most efficient local algorithms to construct: 1) a bounded-degree plane spanner of a UDG (useful for unicasting) and 2) a bounded-degree *lightweight* plane spanner of a UDG (useful for unicasting and broadcasting). I will describe the insights and techniques we developed. There are still questions left open. It is not clear, for example, that the geometry has been fully exploited. Lower bound arguments have also not been made. Finally, we have not dealt with the issue of interference -- critical for battery powered mobile devices. I will finish the talk by bringing up those questions.  
LieuSalle 178 
OrateurLjubomir Perkovic 
UrlSchool of Computing, DePaul University 



Aucun document lié à cet événement.

Retour
Retour à l'index