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.

Topics: Matching (graph theory) (57)%57% related to the paper, Vertex cover (54)%54% related to the paper, Dense graph (52)%52% related to the paper and Randomized algorithm (50)%50% related to the paper

View more info for "Fully Dynamic Maximal Matching in $O(\log n)$ Update Time"

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