Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs

Quinten De Man, Gilvir Gill, Michael A. Bender +2

Dynamic connectivity is a fundamental dynamic graph problem, and recent algorithmic breakthroughs on dynamic graph sketching have reshaped what is theoretically possible: by encodi…