Evènement pour le 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 à l'index