Baswana, Surender ; Gupta, Manoj ; Sen, Sandeep (2011) Fully dynamic maximal matching in O(log n) update time Proceedings  Annual Symposium on Foundations of Computer Science . pp. 383392. ISSN 02725428

PDF
 Author Version
215kB 
Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?...
Related URL: http://dx.doi.org/10.1109/FOCS.2011.89
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 Ivkovíc 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 [5] designed a randomized data structure that achieves O(log^{2} n) expected amortized time for each update for maintaining a capproximate 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.
Item Type:  Article 

Source:  Copyright of this article belongs to IEEE. 
ID Code:  90270 
Deposited On:  08 May 2012 14:37 
Last Modified:  19 May 2016 04:32 
Repository Staff Only: item control page