Publication:4962204

DOI10.1145/2700206zbMath1400.05241arXiv1207.1277OpenAlexW2244920958MaRDI QIDQ4962204

Shay Solomon, Ofer Neiman

Publication date: 30 October 2018

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

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

zbMATH Keywords

maximum matchingdynamic algorithmsmaximal matching

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) Approximation algorithms (68W25)

Related Items (31)

Fully Dynamic Matching in Bipartite Graphs ⋮ Design of Dynamic Algorithms via Primal-Dual Method ⋮ Simultaneously load balancing for every p-norm, with reassignments ⋮ Dynamic algorithms via the primal-dual method ⋮ Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching ⋮ Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries ⋮ Deterministic dynamic matching in worst-case update time ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lazy or eager dynamic matching may not be fast ⋮ Unnamed Item ⋮ Trade-offs in dynamic coloring for bipartite and general graphs ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Dynamic Matching Algorithms in Practice ⋮ Fully dynamic MIS in uniformly sparse graphs ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version) ⋮ Shortest augmenting paths for online matchings on trees ⋮ A simple greedy algorithm for dynamic graph orientation ⋮ Unnamed Item ⋮ Shortest Augmenting Paths for Online Matchings on Trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Unnamed Item ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Improved algorithm for dynamic b-Matching ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time ⋮ Improved Dynamic Graph Coloring ⋮ Unnamed Item

This page was built for publication: Simple Deterministic Algorithms for Fully Dynamic Maximal Matching