Faster Fully Dynamic Matchings with Small Approximation Ratios
From MaRDI portal
Publication:4575628
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
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