Evènement pour le groupe Algorithmique Distribuée


Date 2009-12-04  14:00-15:00
TitreSpanner géométrique planaire de degré au plus 6 
RésuméWe consider the problem of constructing planar spanners of Euclidean graphs with the smallest maximum degree. We present a 6-spanner of degree bound by 6. The best previous bound on the degree of planar spanner was 14 with a stretch of $approx 3.53$. The spanner we proposed can be easily computed the Triangular Distance Delaunay triangulation introduced by Chew in 1989, that is known to have a stretch factor of 2 but its degree may not be bounded. (Travail réalisé en collaboration avec Cyril Gavoille, Nicolas Hanusse et Ljubomir Perković.)  
LieuSalle 178 
OrateurNicolas Bonichon 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index