*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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
