Baswana, Surender; Gupta, Manoj; Sen, Sandeep
(Society for Industrial and Applied Mathematics, 2018-01)
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 ...