Graph Matchings in the Data Stream Model: A Survey
In this talk, we will survey recent work on designing algorithms for
computing graph matchings in the data stream model. This includes
results on finding matchings via linear sketches; estimating the
maximum matching size in low arboricity graphs such as planar
graphs; and multiple-pass algorithms.