ARC Colloquium: Jan van den Brand (Georgia Tech)

Algorithms & Randomness Center (ARC)

Jan van den Brand (Georgia Tech)

August 29, 2022

Klaus 1116 - 11:00 am


Title: Fully Dynamic st-Distances

Abstract: In this talk I will present a fully dynamic algorithm for maintaining approximate distances in a graph.
In particular, given an unweighted and undirected graph G=(V,E) undergoing edge insertions and deletions, two vertices s,t and a parameter 0<ϵ≤1, the dynamic algorithm maintains a (1+ϵ)-approximation of the st-distance  in O(n1.407) time per update (for the current best known bound on the matrix multiplication exponent ω).
At the core, the approach is to combine algebraic data structures with a graph theoretic technique called emulators. This also leads to novel dynamic algorithms for maintaining (1+ϵ,β)-emulators that improve upon the state of the art.


Speaker's Webpage

Videos of recent talks are available at: and

Click here to subscribe to the seminar email list:

Event Details


  • Monday, August 29, 2022
    12:00 pm - 1:00 pm