Fully Dynamic Maximal Matching in O (log n) Update Time

DOI10.1109/FOCS.2011.89MaRDI QIDQ5494978zbMATH OpenOpenAlexFDO

Authors Surender Baswana, Manoj Gupta, 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

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)

Cited in

(20)

• Dynamic algorithms via the primal-dual method
• Shortest augmenting paths for online matchings on trees
• Deterministic dynamic matching in \(O(1)\) update time
• Fully dynamic matching in bipartite graphs
• Design of dynamic algorithms via primal-dual method
• Maintaining Near-Popular Matchings
• Deterministic fully dynamic data structures for vertex cover and matching
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
• Improved algorithm for dynamic b-matching
• An improved algorithm for incremental DFS tree in undirected graphs
• Algorithms for the transportation problem in geometric settings
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• On regularity lemma and barriers in streaming and dynamic matching
• Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set
• Fully dynamic sequential and distributed algorithms for MAX-CUT
• A generalized matching reconfiguration problem
• Dynamic algorithms for submodular matching

This page was built for publication: Fully Dynamic Maximal Matching in O (log n) Update Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494978)