Evènement pour le groupe Algorithmique Distribuée

Date 2011-03-14  14:00-15:00
TitreMultipath spanning graphs 
RésuméThis talk will be about graphs spanners. An (alpha,eta) spanner H of a graph G is a covering subgraph such that for any pair of vertices u,v the distance (defined as the length of a shortest path joining the vertices) in the subgraph is at most alpha times the distance in G plus eta. Generally spanner constructions are rated with the construction time and the size of the spanner they yield. Introduced by Peleg & Alii. spanners are fundamental objects related to compact routing, distance oracles, distributed distance labelling and so on. After a brief remainder of the classic constructions which yield (2k-1,0) (for any positive integer k) and (1,2) spanners we will show it is possible to extend the definition to account other metrics, especially metrics which take in account multiple paths. Firstly we will introduce an *edge*-disjoint multipath metric and show that the two classic constructions can be extended in such a way to create (c(2k-1),0) c-multipath spanners and (2,8) 2-multipath spanners on this metric. Secondly we will show that the notion of spanners is also sensible on *node*-disjoint multipaths by presenting a construction which yields a multiplicative spanner on the metric defined by the smallest *node*-disjoint cycle between two vertices.  
Lieus. 178 
OrateurQuentin Godfroy 

Aucun document lié à cet événement.

Retour à l'index