Fully dynamic connectivity in O(log n(log log n)2) amortized expected time
Part Of
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Start Page
510
End Page
520
ISBN (of the container)
978-161197478-2
Date Issued
2017-01
Author(s)
Abstract
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 log n)2) factor of a lower bound due to Patrascu 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.
Event(s)
28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Publisher
Society for Industrial and Applied Mathematics
Type
conference paper