Theory Seminar
Fully Dynamic Connectivity in O(log n(log log n)^2) Amortized Expected Time
Shang-En HuangUniversity of Michigan
WHEN:
Friday, January 6, 2017 @ 10:30 am
Add to Google Calendar
Add to Google Calendar
SHARE:
p>Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with O(log n(log log n)^2) amortized expected update time and O(log n/(log log log n)) query time, which comes within an O((log logn)^2) factor of a lower bound due to Paringcu and Demaine. The new structure is based on a dynamic connectivity algorithm proposed by Thorup in an extended abstract at STOC 2000, which left out some important details.
This work is co-worked with Dawei Huang, Tsvi Kopelowitz and Seth Pettie.