Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time

Jianer Chen, Qin Huang, Iyad Kanj +2

We present streaming algorithms for the graph $k$-matching problem in both the insert-only and dynamic models. Our algorithms, with space complexity matching the best upper bounds,…