AI Lab logo
menu MENU

Theory Seminar

Graph Matchings in the Data Stream Model: A Survey

Andrew McGregorProfessorUniversity of Massachusetts at Amherst
SHARE:

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