Abstract:
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(tlog n + n log2 n) with high probability