Maximum Matching in Semi-Streaming with Few Passes

Christian Konrad, Frédéric Magniez, Claire Mathieu

In the semi-streaming model, an algorithm receives a stream of edges of a graph in arbitrary order and uses a memory of size $O(n \mbox{ polylog } n)$, where $n$ is the number of v…