Maintaining a large matching and a small vertex cover

DOI10.1145/1806689.1806753zbMath1293.05305OpenAlexW2096413587MaRDI QIDQ2875173

Ronitt Rubinfeld, Krzysztof Onak

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806753

zbMATH Keywords

data structuresmaximum matchingdynamic algorithmsvertex cover

Mathematics Subject Classification ID

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

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 ⋮ 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 ⋮ 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) ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Improved algorithm for dynamic b-Matching ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time ⋮ Unnamed Item

This page was built for publication: Maintaining a large matching and a small vertex cover