# Διάλεξη του κ Laurent Viennot, 3/7/2019

Την Τετάρτη 03 Ιουλίου 2019 στις 14:00 στην αίθουσα Α56 του Τμήματος Πληροφορικής και Τηλεπικοινωνιών του Εθνικού και Καποδιστριακού Πανεπιστημίου Αθηνών θα πραγματοποιηθεί διάλεξη του κ Laurent Viennot.

Το θέμα της διάλεξης είναι:   Graph properties of road networks and efficient distance labeling

Περίληψη: 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 \emph{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$. 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 \emph{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. We also present extension of this work towards generalizing the hub labeling approach on one side and towards analyzing the size of hub labels in general sparse graphs on the other side.

Joint work with Siddharth Gupta, Adrian Kosowski and Przemyslaw Uznanski.

Οι φοιτητές του παλαιού ΠΜΣ, στο πλαίσιο των υποχρεώσεών τους, μπορούν να παρακολουθήσουν την παραπάνω διάλεξη και να προσκομίσουν στη Γραμματεία τη σχετική βεβαίωση http://www.di.uoa.gr/sites/default/files/beb_seminariou.docx