Semi-Streaming Matching in a Single Pass II: Greedy is OptimalResearch Paper
A large graph can have far more edges than vertices. Keeping every edge in memory may therefore be impractical even when retaining a few records for each vertex is affordable. The semi-streaming model asks what can be computed under this limitation when edges arrive sequentially. For maximum matching, a simple greedy procedure retains an arriving edge…