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

David Gibb, Bruce Kapron, Valerie King +1

This paper considers fully dynamic graph algorithms with both faster worst case update time and sublinear space. The fully dynamic graph connectivity problem is the following: give…