Ομιλητής: Αντώνης Σκαρλάτος (University of Salzburg, απόφοιτος ΑΛΜΑ)
Τίτλος: Bootstrapping Dynamic Distance Oracles
Ημερομηνία: 16-5-2024, 13:00
Αίθουσα: A56, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Σύνοψη
The input for many applications can be naturally modelled as a graph, for instance a network of people or a network of roads. One of the most fundamental and well-studied problems is to construct a distance oracle in order to solve the All-Pairs Shortest Paths problem. In this problem, given a weighted graph the goal is to produce a succinct data structure that upon queries is able to return approximate distances between any source-target vertex pair. In the real world where everything changes all the time, the relations between the vertices of the graph may change over time. That is, edges may be deleted from the graph or new edges may be inserted to the graph. The goal then is to design an approximate All-Pairs Distance Oracle in the fully dynamic setting with good guarantees while the graph is subject to edge updates.
Prior works either suffer from a large approximation guarantee or from a large update time. In this talk, we give the first constant-stretch fully dynamic distance oracle with small polynomial update time. The idea is to produce a faster fully dynamic distance oracle through an existing decremental algorithm and a slower fully dynamic algorithm, and then repeatedly apply this reduction until we obtain the desired fully dynamic algorithm.
This is a joint work with Sebastian Forster, Gramoz Goranci, and Yasamin Nazari, and it appeared in the proceedings of ESA 2023.