Intro

The intent of this is to give a high level overview of the two algorithms presented in “Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time”. For a full understanding look to the paper. I attempted to explain concepts to the best of my ability to better understand the paper myself and although I believe my work to be a correct representation of the paper there is a chance I misunderstood there explanations. If in doubt look to the original paper.

I laid out my understanding in two sections. Insert Model and the Dynamic Model although the paper discusses more for example on why W is required as a parameter in the update time I do not discuss this directly or there proof of it. Instead I did my best to present in a linear fashion the previous work and topics to understand how and why these algorithms work the way they do at a High Level. For an in depth understanding see the paper. The Insert Model post contains the Intro to the problem. Background on what was done before to understand the significance of the Insert and Dynamic algorithms. Tools and concepts to understand the algorithms. Then the Insert Algorithm. The Dynamic Model follows with the tools and concepts needed to understand then presents the dynamic algorithm.

To reiterate again this is a high level view of my understanding of what they did in the paper thus although I provided my breakdown of a couple lemmas. It is not comprehensive only in depth enough for myself to understand how both of these algorithms work while guaranteeing the given bound in space and update time per edge.