Abstract. We present algorithms for finding large graph matchings in the streaming model. In this model, applicable when dealing with massive graphs, edges are streamed-in in some arbitrary order rather than residing in randomly accessible memory. For ǫ > 0, we achieve a 1 1+ǫ approximation for maximum cardinality matching and a 1 2+ǫ approximation to maximum weighted matching. Both algorithms use a constant number of passes andÕ(|V |) space.
When considering multi-pass algorithms, REF gave a (1 − ε)-approximation algorithm using
Finding graph matchings in data streams
APPROX-RANDOM
Mathematics Computer Science