|
Evènement pour le groupe Séminaire du LaBRI
Date | 2010-10-21 14:00-15:00 |
Titre | Sé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. |
Lieu | Amphi LaBRI |
Orateur | Prosenjit Bose |
Url | Carleton University, Canada |
Aucun document lié à cet événement. RetourRetour à l'index
| |