(1 + ∊)-Approximate Incremental Matching in Constant Deterministic Amortized Time

DOI10.1137/1.9781611975482.114zbMath1432.68354OpenAlexW4211172364MaRDI QIDQ5236300

Schwiegelshohn Chris, Fabrizio Grandoni, Solomon Shay, Piotr Sankowski, Stefano Leonardi

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975482.114

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (2)

Deterministic dynamic matching in worst-case update time ⋮ Dynamic Matching Algorithms in Practice

This page was built for publication: (1 + ∊)-Approximate Incremental Matching in Constant Deterministic Amortized Time