Streaming Algorithms for Matchings
2nd October 2018, 11:00 am – 12:00 pm
Howard House, 4th Floor Seminar Room
In the graph streaming model, an algorithm processes the edges of an input graph one by one while maintaining a memory that is sublinear in the number of edges. In this talk, I will discuss how to compute large matchings in this model. I will both discuss the problem's long history as well as one of my recent works in this area (Konrad, MFCS 2018).