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.
(1 + ε)-approximate incremental matching in constant deterministic amortized time / Grandoni, F.; Leonardi, S.; Sankowski, P.; Schwiegelshohn, C.; Solomon, S.. - (2019), pp. 1886-1898. (Intervento presentato al convegno 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 tenutosi a San Diego; United States).
(1 + ε)-approximate incremental matching in constant deterministic amortized time
Grandoni F.;Leonardi S.;Sankowski P.;Schwiegelshohn C.
;
2019
Abstract
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
Grandoni_Approximate_2019.pdf
accesso aperto
Note: https://epubs.siam.org/doi/10.1137/1.9781611975482.114
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
642.45 kB
Formato
Adobe PDF
|
642.45 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
