Faster Fully Dynamic Matchings with Small Approximation Ratios

DOI10.1137/1.9781611974331.ch50zbMath1409.68203OpenAlexW4235789583MaRDI QIDQ4575628

Aaron Bernstein, Clifford Stein

Publication date: 16 July 2018

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (18)

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching ⋮ Deterministic dynamic matching in worst-case update time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Round Compression for Parallel Matching Algorithms ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Dynamic Matching Algorithms in Practice ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version) ⋮ A simple greedy algorithm for dynamic graph orientation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Unnamed Item ⋮ Improved algorithm for dynamic b-Matching ⋮ Maximum matching on trees in the online preemptive and the incremental graph models ⋮ Improved Dynamic Graph Coloring ⋮ Unnamed Item ⋮ Distributed algorithms for matching in hypergraphs

This page was built for publication: Faster Fully Dynamic Matchings with Small Approximation Ratios