Theory Seminar

Graph Matchings in the Data Stream Model: A Survey

Andrew McGregorProfessorUniversity of Massachusetts at Amherst

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.

Sponsored by

Theory Group

Faculty Host

Seth Pettie