Get all the updates for this publication

Articles

Fully dynamic maximal matching in O(log n) update timePublished in Society for Industrial and Applied Mathematics Publications

2015

DOI: 10.1137/130914140

Volume: 44

Issue: 1

Pages: 88 - 113

We present an algorithm for maintaining 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. While there exists a trivial O (n) time algorithm for each edge update, the previous best known result for this problem is due to Ivković and Lloyd [Lecture Notes in Comput. Sci. 790, Springer-Verlag, London, 1994, pp. 99-111]. For a graph with n vertices and m edges, they gave an O ((n + m)0. 7072) update time algorithm which is sublinear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfeld [ Proceedings of STOC'10, Cambridge, MA, 2010, pp. 457-464] designed a randomized algorithm that achieves expected amortized O (log 2n) time for each update for maintaining a capproximate maximum matching for some unspecified large constant c . In contrast, we can maintain a factor 2 approximate maximum matching in expected amortized O (log n) time per update as a direct corollary of the maximal matching scheme. This in turn also implies a 2-approximate vertex cover maintenance scheme that takes expected amortized O (log n ) time per update. © 2015 Society for Industrial and Applied Mathematics.

Postprint Version

Content may be subject to copyright.

About the journal

Published in Society for Industrial and Applied Mathematics Publications

Open Access

Impact factor

N/A