Lundi 23 novembre, Amphi LaBRI:
12h45-14h: repas au "Carpe Diem"
14h-15h: Laurent Viennot - From compact routing to distance oracles and spanners
15h-15h30: Laurent Feuilloley - Locally Optimal Load Balancing
15h30-16h: Nicolas Blanchard - Dynamic Facility Location : Minimizing Sum of Radii
16h-16h30: pause café
16h30-17h30: Victor Chépoï - Isometric and low-distortion l1-embeddings
17h30h-19h: discussions et réflexion sur le GT CoA et le GDR IM
Mardi 24 novembre, Amphi LaBRI:
9h30-10h30: Nicolas Bonichon - Spanners géométriques
10h30-11h: pause café
11h-11h30: Arnaud Labourel - Rendez-vous in Networks in Spite of Delay Faults
11h30-12h: Ralf Klasing - Efficiently Testing T -Interval Connectivity in Dynamic Graphs
12h-12h30: Nicolas Schabanel - Folding Turing is hard but feasible
12h45-14h: repas au "Carpe Diem"
From compact routing to distance oracles and spanners
A classical area of research is devoted to compact data-structures in networks. Among all, the most prominent algorithmic problem of networks consists in routing. This basically consists in assigning some table at each node of a network and some label identifying each destination so that given its table and the label of the destination of a packet, a node can decide where to forward the packet. Many results of the domain concerns the trade-off between the quantity of information that is stored at each node and the quality of the routes this information provide. We will see that this problem is related to that of finding a spanner of the network that is a subgraph which approximates the original graph of the network with respect to distances: how many links can you remove from a graph without stretching too much distances? This also leads to the problem of finding a compact distance oracle, that is a data structure that approximates the distances inside a graph. The distributed version of the problem consists in assigning a small label to each node so that an estimation of the distance between two nodes can be computed from their two labels (without any auxiliary data-structure). Finally, we will see that this kind of techniques have recently been applied to road networks where distance labels offer an elegant solution for computing driving directions.
Isometric and low-distortion l_1-embeddings
In the first part of the talk, I will survey the main known results about isometric and low-distortion embeddings of metric spaces and graphs into l_1-spaces and mention some algorithmic applications. In the second part of the talk, I will present our recent result with J. Chalopin and G. Naves about isometric embeddings of Busemann surfaces into the L_1-space based on a combinatorial Crofton formula.
Spanners géométriques
L'étirement d'un graphe géométrique est le pire rapport entre la distance dans le graphe et la distance Euclidienne, pour toute paire de points du graphe. Un t-spanner est un graphe (ou une famille de graphes) dont l'étirement est borné par t. Dans cet exposé je présenterai quelques résultats relatifs à certains spanners : triangulations de Delaunay, Theta-graphs, spanners de degré borné,...