Fully dynamic $3/2$ approximate maximum cardinality matching in $O(\sqrt{n})$ update time

Manas Jyoti Kashyop, N. S. Narayanaswamy

We present a randomized algorithm to maintain a maximal matching without 3 length augmenting paths in the fully dynamic setting. Consequently, we maintain a $3/2$ approximate maxim…