(1 + ε-Approximate incremental matching in constant deterministic amortized time
Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, Shay Solomon · Symposium on Discrete Algorithms · 2019
We study the matching problem in the incremental setting, where we are given a sequence of edge insertions and aim at maintaining a near-maximum cardinality matching of the graph with small update time. We present a deterministic algorithm that, for any constant e > 0, maintains a (1 + e)-approximate matching with constant amortized update time per insertion.