Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

DOI10.1137/1.9781611973730.54zbMath1372.68071OpenAlexW2951652158MaRDI QIDQ5362993

Giuseppe F. Italiano, Sayan Bhattacharya, Monika R. Henzinger

Publication date: 5 October 2017

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

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Data structures (68P05) Approximation algorithms (68W25)

Related Items (20)

Fully Dynamic Matching in Bipartite Graphs ⋮ Design of Dynamic Algorithms via Primal-Dual Method ⋮ Maintaining Near-Popular Matchings ⋮ Dynamic algorithms via the primal-dual method ⋮ Dynamic rank-maximal and popular matchings ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic clustering to minimize the sum of radii ⋮ Round Compression for Parallel Matching Algorithms ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Improved algorithm for dynamic b-Matching ⋮ Dynamic kernels for hitting sets and set packing ⋮ Unnamed Item

This page was built for publication: Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching