Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

Sagar Kale, Sumedh Tirodkar

We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our m…