New deterministic approximation algorithms for fully dynamic matching

DOI10.1145/2897518.2897568zbMath1376.68169arXiv1604.05765OpenAlexW2341465683MaRDI QIDQ5361847

Sayan Bhattacharya, Danupon Nanongkai, Monika R. Henzinger

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.05765

zbMATH Keywords

data structuresdynamic graph algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Approximation algorithms (68W25)

Related Items (18)

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching ⋮ Deterministic dynamic matching in worst-case update time ⋮ Dynamic rank-maximal and popular matchings ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ Dynamic clustering to minimize the sum of radii ⋮ 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) ⋮ Unnamed Item ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Constructing light spanners deterministically in near-linear time ⋮ Improved algorithm for dynamic b-Matching ⋮ Unnamed Item

This page was built for publication: New deterministic approximation algorithms for fully dynamic matching