School of Computer Science, Electrical and Electronic Engineering, and Engineering Maths PGR ConferenceSCEEM PGR

Virtual, University of Bristol
2021

This was an internal conference held for postgraduate research (PGR) students in the School of Computer Science, Electrical and Electronic Engineering, and Engineering Maths (SCEEM) to showcase their research. My talk was on the following:

On Two-Pass Streaming Algorithms for Maximum Bipartite Matching

Abstract

In the semi-streaming model, proposed by Feigenbaum et al. [ICALP 2004], a graph with n vertices is presented to an algorithm as a stream of edges where the algorithm maintains a memory of size $O(n \textrm{ polylog } n)$. It provides an efficient model for processing massive graphs which have quickly become widespread.

Finding a maximum bipartite matching is a fundamental graph problem which has numerous real-world applications and has garnered great attention in this model. In this talk, I will cover the best known algorithms and lower bounds using two passes of the stream. This is based on joint work with Dr Christian Konrad.

Conference talk | Slides