Streaming Maximal Matchin
Streaming Maximal Matching with Bounded Deletions
Streaming Maximal Matching with Bounded Deletions
arXiv:2502.15330v1 Announce Type: new
Abstract: 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 deletions, where the number of insertions is unrestricted but the number …
