Streaming Maximal Matching with Bounded Deletions

Sanjeev Khanna, Christian Konrad, Jacques Dark

We initiate the study of the Maximal Matching problem in bounded-deletion graph streams. In this setting, a graph $G$ is revealed as an arbitrary sequence of edge insertions and de…