Home » Publication » 19666

Dettaglio pubblicazione

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.

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.
Gruppo di ricerca: Algorithms and Data Science
keywords
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma