Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version)
From MaRDI portal
Publication:4641588
DOI10.1137/16M1106158zbMath1387.05188MaRDI QIDQ4641588
Surender Baswana, Manoj Gupta, Sandeep Sen
Publication date: 18 May 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (3)
Upper and lower bounds for fully retroactive graph problems ⋮ Unnamed Item ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fully-dynamic min-cut
- Matching theory
- Maintaining a large matching and a small vertex cover
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Fully dynamic randomized algorithms for graph spanners
- Fully Dynamic Matching in Bipartite Graphs
- Popular Matchings
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Faster scaling algorithms for general graph matching problems
- Faster Fully Dynamic Matchings with Small Approximation Ratios
- Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
- Cuckoo hashing
- Matching, Euler tours and the Chinese postman
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
- Paths, Trees, and Flowers
- New deterministic approximation algorithms for fully dynamic matching
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Algorithms – ESA 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- College Admissions and the Stability of Marriage
This page was built for publication: Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version)
