Evènement pour le groupe
Algorithmique Distribuée
| Date | 2009-12-04 14:00-15:00 |
| Titre | Spanner 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ć.)
|
| Lieu | Salle 178 |
| Orateur | Nicolas Bonichon |
| Url | LaBRI |
Aucun document lié à cet événement.
RetourRetour à l'index