Tight Bounds for Vertex Connectivity in Dynamic Streams
Tight Bounds for Vertex Connectivity in Dynamic Streams
We present a streaming algorithm for the vertex connectivity problem in dynamic streams with a (nearly) optimal space bound: for any n-vertex graph G and any integer k ≥ 1, our algorithm with high probability outputs whether or not G is k-vertex-connected in a single pass using Õ(kn) space1.Our upper …