Dynamic connectivity is one of the most fundamental problems in dynamic graphalgorithms. We present a randomized Las Vegas dynamic connectivity datastructure with $$O(\log n(\log\log n)^2)$$ amortized expected update time and$$O(\log n/\log\log\log n)$$ worst case query time, which comes very close to thecell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup(2011).
more »
« less
Log BPS Numbers of Log Calabi-Yau Surfaces
- Award ID(s):
- 1802242
- PAR ID:
- 10227480
- Date Published:
- Journal Name:
- Transactions of the American Mathematical Society
- ISSN:
- 0002-9947
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
An official website of the United States government

