(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time
Lists
Only you see this
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.
BibTeX
@inproceedings{grandoni2019approximate,
author = {Fabrizio Grandoni and Stefano Leonardi and Piotr Sankowski and Chris Schwiegelshohn and Shay Solomon},
title = {{(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time}},
booktitle = {SODA},
year = {2019},
doi = {10.1137/1.9781611975482.114},
}Loading related content...