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 log2 n) with high probability. © 2018 Society for Industrial and Applied Mathematics.

Sandeep Sen

(SoE) School of Engineering

S. Baswana

M. Gupta

<p>Shiv Nadar University is a comprehensive, multidisciplinary, research-focused, and student-centric University offering a full range of academic programs at the undergraduate, postgraduate and doctoral level. With state-of-the-art infrastructure, the University comprises of academic wings, sophisticated labs, international standard sports facilities, amphitheaters, auditorium, conference rooms and smart classrooms. The University&rsquo;s goal is to become internationally recognized for the quality of its research and creative endeavors and their applicability to improving quality of life, generating new insights and expanding the boundaries of human knowledge creativity. Committed to excellence in teaching, research and service, the University aims to serve the higher education needs of India and the world beyond.</p>