Maintaining a large matching and a small vertex cover
From MaRDI portal
Publication:2875173
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
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
