Fully Dynamic Maximal Matching in O (log n) Update Time
Authors:
- Surender BaswanaSBSurender Baswana
- Manoj GuptaMGManoj Gupta
- Sandeep SenSSSandeep Sen
- 1 October 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 383-392
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 was due to Ivkovic and Llyod[4]. For a graph with n vertices and m edges, they give 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 [6] designed a randomized data structure that achieves O(log2 n) expected 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 amortized 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 amortized time per update.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Maintaining a large matching and a small vertex cover2010
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithmsTheoretical Computer Science, 2007
- Cuckoo hashingJournal of Algorithms, 2004
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivityJournal of the ACM, 2001
- Randomized fully dynamic graph algorithms with polylogarithmic time per operationJournal of the ACM, 1999
- Average-Case Analysis of Dynamic Graph AlgorithmsAlgorithmica, 1998
- Fully dynamic maintenance of vertex cover1994
- An O(v|v| c |E|) algoithm for finding maximum matching in general graphs1980