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: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121

Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu

Event Details

Date/Time:

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