Fully dynamic maximal matching in O(log n) update time
Preprint
Abstract
We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes O(log n) expected amortized time for each edge update where n is the number of vertices in the graph. While there is a trivial O(n) algorithm for edge update, the previous best known result for this problem for a graph with n vertices and m edges is O({(n+ m)}^{0.7072})which is sub-linear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfield designed a randomized data structure that achieves O(log^2 n) amortized time for each update for maintaining a c-approximate maximum matching for some large constant c. In contrast, we can maintain a factor two approximate maximum matching in O(log n) expected time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes O(log n) expected time per update.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Dynamic Approximate All-Pairs Shortest Paths in Undirected GraphsSIAM Journal on Computing, 2012
- Improved Dynamic Reachability Algorithms for Directed GraphsSIAM Journal on Computing, 2008
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithmsTheoretical Computer Science, 2007
- Fully-Dynamic Min-Cut*Combinatorica, 2007
- Popular MatchingsSIAM Journal on Computing, 2007
- Maximum Matchings via Gaussian Elimination2004
- Average-Case Analysis of Dynamic Graph AlgorithmsAlgorithmica, 1998
- Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related ProblemsSIAM Journal on Computing, 1994
- Matching, Euler tours and the Chinese postmanMathematical Programming, 1973
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973