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 ε > 0, maintains a (1 + ε)-approximate matching with constant amortized update time per insertion.
2019, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Pages 1886-1898
(1 + ε)-approximate incremental matching in constant deterministic amortized time (04b Atto di convegno in volume)
Grandoni F., Leonardi S., Sankowski P., Schwiegelshohn C., Solomon S.
Gruppo di ricerca: Algorithms and Data Science