Fully Dynamic Maximal Matching in O (log n) Update Time
Fully Dynamic Maximal Matching in O (log n) Update Time
复制标题
O (log n) 更新时间内的完全动态最大匹配
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Sandeep Sen
中科院分区：
文献类型：
--
作者：
Surender Baswana;Manoj Gupta;Sandeep Sen
我们提出了一种算法，用于在添加和删除边缘下在图中保持最大匹配。我们的数据结构是随机的，需要$ o（log n）$预期的每个边缘更新时间，其中$ n $是图中的顶点。虽然有一个琐碎的$ o（n）$算法用于边缘更新，但此问题的先前最佳结果是由于ivkovi'c和llyodcite {llyod}。对于具有$ n $顶点和$ m $边缘的图形，它们给出了$ o（{（n+ m）}^{0.7072}）$更新时间算法，该算法仅适用于稀疏图。据我们所知，％的％是最大匹配的第一个polygog更新时间，这意味着与以前的结果相比，指数级提高了％。对于最大匹配的相关问题，Onak和Rubinfeld引用{onak}设计了一个随机数据结构，可实现$ O（log^2 n）$预期的每次更新的预期摊销时间，以维持$ c $ app的最大匹配常数$ c $。相比之下，我们可以将$ O（log n）$预期摊销时间的最大匹配度保持在最大匹配方案的直接推论中。反过来，这也意味着一个两个近似的顶点盖维护方案，该方案需要$ O（log n）$预期的每次更新时间。
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 Ivkovi'c and Llyodcite{llyod}. For a graph with $n$ vertices and $m$ edges, they give an $O( {(n+ m)}^{0.7072})$ update time algorithm which is sub linear only for a sparse graph. %To the best of our knowledge this %is the first polylog update time for maximal matching that implies an % exponential improvement from the previous results. For the related problem of maximum matching, Onak and Rubinfeld cite{onak} designed a randomized data structure that achieves $O(log^2 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.