Dynamic Algorithms for Maximum Matching Size
Soheil Behnezhad · Society for Industrial and Applied Mathematics eBooks · 2023
We study fully dynamic algorithms for maximum matching. This is a well-studied problem, known to admit several update-time/approximation trade-offs. For instance, it is known how to maintain a 1/2-approximate matching in (poly log n) update time or a 2/3-approximate matching in update time, where n is the number of vertices. It has been a long-standing open problem to determine whether either of these bounds can be improved.