Evènement pour le groupe Algorithmique Distribuée


Date 2015-06-22  14:00-15:00
TitreUpper and Lower Bounds for Online Routing on Delaunay Triangulations 
Résumé Consider a weighted graph G whose vertices are points in the plane and edges are line segments between pairs of points. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on G has a routing ratio of c if the length of the path produced by the algorithm from any vertex s to any vertex t is at most c|[st]|. The routing algorithm is online if it makes forwarding decisions based on 1) the k-neighborhood in G (for some integer constant k > 0) of the current position of the message and 2) limited information stored in the message header. We present an online routing algorithm on the Delaunay triangulation with routing ratio less than 5.90. This improves upon the algorithm with best known routing ratio of 15.48. We also show that the routing ratios of any deterministic k-local algorithm is at least 1.70 for the Delaunay triangulation.  
Lieu178 
OrateurNicolas Bonichon 



Aucun document lié à cet événement.

Retour
Retour à l'index