Fully dynamic maximal matching in O(log n) update time

Details Fully dynamic maximal matching in O(log n) update time Fully dynamic maximal matching in O(log n) update time

2011-03-06

arxiv.org/abs/1103.1109v2

Computer Science

Data Structures and Algorithms

16 pages, 3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Fully dynamic maximal matching in O(log n) update time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fully dynamic maximal matching in O(log n) update time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fully dynamic maximal matching in O(log n) update time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-418597