Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version)
Surender Baswana, Manoj Kumar Gupta, Sandeep Sen · SIAM Journal on Computing · 2018
We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized $O(\log n)$ time for each edge update, where $n$ is the number of vertices in the graph. Moreover, for any sequence of $t$ edge updates, the total time taken by the algorithm is $O(t\log n + n \log^2 n)$ with high probability. (Original article at https://doi.org/10.1137/130914140.)