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.
|