1 citations · 3 across the 3 of their papers we have counts for
3 papers
cs.DS2022★ 1 cited
Tight Bounds for Vertex Connectivity in Dynamic Streams
Sepehr Assadi, Vihan Shah
We present a streaming algorithm for the vertex connectivity problem in dynamic streams with a (nearly) optimal space bound: for any -vertex graph and any integer …
cs.DS2022★ 1 cited
Space Optimal Vertex Cover in Dynamic Streams
Kheeran K. Naidu, Vihan Shah
We optimally resolve the space complexity for the problem of finding an -approximate minimum vertex cover (MVC) in dynamic graph streams. We give a randomised algorithm for $…
cs.DS2022★ 1 cited
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams
Sepehr Assadi, Vihan Shah
We present an algorithm for the maximum matching problem in dynamic (insertion-deletions) streams with *asymptotically optimal* space complexity: for any -vertex graph, our algo…