Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified FrameworkResearch Paper
A semi-streaming algorithm reads the edges of an -vertex graph as a stream, possibly several times, and keeps only bits of memory. Matching is the central problem of this model: the output itself can have edges, so the model allows just enough memory to write it down, and the question is how many passes over the stream a …