Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints

Zemin Chao, Jianhe Cen, Hengzhao Ma +1

We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of $v$-vertex simple graphs with failure probability at most $\delta$. Nelson and Yu proved…