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.
---------------------------------------------------------------
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
