Dynamic graph connectivity with improved worst case update time and sublinear space

Built on

O jistem problemu minimalnim (about a certain minimal problem) (in czech, german summary)
Otakar Boru̇vka · 1926
Earlier work this paper cites.
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Monika R. Henzinger and Valerie King · 1999
Earlier work this paper cites.
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup · 2001
Earlier work this paper cites.

Analyzing graph structure via linear measurements
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2012
Cited alongside, same era.
Dynamic graph connectivity in polylogarithmic worst case time
Bruce M. Kapron, Valerie King, and Ben Mountjoy · 2013
Cited alongside, same era.

A unifying framework for ℓ \ell 0-sampling algorithms
Graham Cormode and Donatella Firmani · 2014
Later among the works it cites.
Sample(x)=(a*x<=t) is a distinguisher with probability 1/8
Original
Mikkel Thorup · 2014
Later among the works it cites.