Christian Konrad

University of Bristol

Streaming Algorithms for Matchings

Combinatorics Seminar

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).

Organisers: David Ellis, Tom Johnston

Comments are closed.