‘Dynamic Algorithms for Maximum Matching Size’

“We study fully dynamic algorithms for maximum matching. This is a well-studied problem, known to admit several update-time/approximation trade-offs. … It has been a long-standing open problem to determine whether either of these bounds can be improved. In this paper, we show that when the goal is to maintain just the size of the matching (and not its edge-set), then these bounds can indeed be improved.”

View on Site: ‘Dynamic Algorithms for Maximum Matching Size’