Deterministic Dynamic Matching In Worst-Case Update Time

Peter Kiss

We present deterministic algorithms for maintaining a $(3/2+\epsilon )$ and $(2+\epsilon )$-approximate maximum matching in a fully dynamic graph with worst-case update times $\hat{O}(\sqrt{n}…