Baswana, SurenderSurenderBaswanaGupta, ManojManojGuptaSen, SandeepSandeepSen2025-08-302025-08-302018-01-0110.1137/16M11061582-s2.0-85049431578http://repository.iitgn.ac.in/handle/IITG2025/22977We 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² n) with high probability.falseDynamic graph algorithm | MatchingArticle10957111617-650201831arJournal15WOS:000437012600001