Distance Computation in Massive Graphs

10^th November 2022, 16:00
Michal Dory
University of Haifa, Israel

Abstract

Computing distances in a graph is one of the most fundamental problems in graph algorithms. But how can we solve it when the input graph is too large and cannot be stored in one computer? In this talk, I will discuss a recent line of work that led to extremely fast distributed algorithms for approximating shortest paths, improving exponentially over the state-of-the-art.