Fully Dynamic Maximal Matching in O (log n) Update Time
From MaRDI portal
Publication:5494978
DOI10.1109/FOCS.2011.89zbMath1292.68039OpenAlexW2146343385MaRDI QIDQ5494978
Manoj Gupta, Surender Baswana, Sandeep Sen
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/focs.2011.89
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items (15)
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 Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Shortest augmenting paths for online matchings on trees ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Improved algorithm for dynamic b-Matching ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: Fully Dynamic Maximal Matching in O (log n) Update Time
