Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 25, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Goran Zuzic (Google Research)
Single-source shortest path computations are important building blocks for many algorithm like maximum flows, graph embeddings, clusterings, etc. However, these higher-level application assume the shortest-path computation is exact and relaxing this condition typically breaks the application. On the other hand, computing exact shortest paths in parallel and distributed settings seems significantly more complicated than their approximate counterparts.
We introduce stronger notions of approximate single-source shortest-path distances. We show how to efficiently compute them from weaker standard notions, and demonstrate the algorithmic power of these new notions and transformations. One application is the first work-efficient parallel algorithm (i.e., that uses O~(m) work) for computing exact single-source shortest paths graphs with strictly sublinear depth --- resolving a major open problem in parallel computing.
Joint work with Václav Rozhoň, Bernhard Haeupler, Anders Martinsson, and Christoph Grunau.
Automatic MiSe System Software Version 1.4803M | admin login