Theory Seminar

Graph Matchings in the Data Stream Model: A Survey

Andrew McGregor

University of Massachusetts at Amherst
Friday, January 19, 2018
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

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.

Additional Information

Contact: Seth Pettie

Phone: 5-4210

Email: pettie@umich.edu

Sponsor(s): Theory Group

Faculty Sponsor: Seth Pettie

Open to: Public

Web Page: https://people.cs.umass.edu/~mcgregor/