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

Intitulé:   
Sém LaBRI. On Plane Geometric Spanners
du groupe Séminaire du LaBRI

Date 2010-10-21  14:00-15:00
TitreSém LaBRI. On Plane Geometric Spanners 
RésuméA geometric graph $G$ is a graph whose vertices are points in the plane and whose edges are line segments weighted by the Euclidean distance between their endpoints. In this setting, a $t$-spanner of $G$ is a spanning subgraph $G'$ with the property that for every pair of vertices $x, y$, the shortest path from $x$ to $y$ in $G'$ has weight at most $t geq 1$ times the shortest path from $x$ to $y$ in $G$. The parameter $t$ is commonly referred to as the {em spanning ratio}, the {em dilation} or the {em stretch factor}. In addition to having bounded spanning ratio, it is desireable to build $t$-spanners that possess other properties, such as bounded degree, low weight, or fault-tolerance to name a few. In this talk, we are particularly interested in planarity. We review various results in the literature on how to build spanners that are planar. 
LieuAmphi LaBRI 
OrateurProsenjit Bose 
UrlCarleton University, Canada 



Aucun document lié à cet événement.

Retour
Retour à l'index