Laurent VIENNOT - Research Scientist, INRIA Data Science
Date: - Location: Eurecom
Date: Thu, 2017-02-23 14:30 - 15:30 Location: EURECOM, room 101 Speaker: Laurent Viennot Speaker's affiliation: Inria Abstract: The goal of a hub-based distance labeling scheme for a network $G = (V, E)$ is to assign a small subset $S(u) \subseteq V$ to each node $u \in V$, in such a way that for any pair of nodes $u, v$, the intersection of hub sets $S(u) \cap S(v)$ contains a node on the shortest $uv$-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least $r$ intersecting a given ball of radius $2r$. In this talk, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size. Joint work with Adrian Kosowski Speaker's bio: Laurent Viennot works on graph and network algorithms. He is a senior research scientist at french national institute on computer science Inria. His research interests span ad hoc routing, peer-to-peer networking and spanner theory. After a PHD at Paris Diderot University on graph algorithms, he joined Inria in 1998 to work on ad hoc networks in the Hipercom team. He has also been a part time teacher at Ecole Polytechnique for 7 years. He is now leader of the "GANG" Inria project-team on network and graph algorithms hosted at Irif in Paris Diderot University.
