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

Titre:   
Competitive Routing on a Variant of the Delaunay Triangulation

Date 2012-11-26  14:00-15:00
NomCompetitive Routing on a Variant of the Delaunay Triangulation 
DescriptionA subgraph H of a weighted graph G is a t-spanner of G provided that for every edge xy in G, the weight of the shortest path between x and y in H is at most t times the weight of xy. It is known that the Delaunay triangulation of a point set P (where the empty region is an equilateral triangle) is a 2-spanner of the complete Euclidean graph. We present a new and simple proof of this spanning ratio that allows us to route competitively on this graph. Specifically, we present a deterministic local routing scheme that is guaranteed to find a short path between any pair of vertices in this Delaunay triangulation. We guarantee that the length of the path is at most 5/sqrt(3) times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising since the spanning ratio is 2. Finally, we showed how this routing scheme can be extended to route on some bounded degree subgraphs of this Delaunay triangulation.  
LieuSalle 178 
ContactProsenjit Bose (Carleton University) 
ThèmeAlgorithmique Distribuée 



Aucun document lié à cet événement.

Retour
Retour à l'index