Simple deterministic algorithms for fully dynamic maximal matching
Simple deterministic algorithms for fully dynamic maximal matching
复制标题
用于完全动态最大匹配的简单确定性算法
DOI：
10.1145/2488608.2488703
复制
发表时间：
2012
影响因子：
4.4
通讯作者：
Shay Solomon
中科院分区：
文献类型：
--
作者：
Ofer Neiman;Shay Solomon
最大匹配可以维持完全动态的（支持边缘的加法和删除）N-vertex图，并使用琐碎的确定性算法，而o（n）的最差案例更新时间均优于n no nesightiantiant算法。 ）据报道，这一方向的唯一进展是由于Ivkovic和Lloyd [14]，他们在1993年设计了一种确定性算法，其摊销的更新时间（（N+M）√2/2） ，其中m是边的数量。
在本文中，我们表明了第一个确定性的完全动态算法，以胜过琐碎的算法。 - 我们指出的是，在此工作之前已经知道了在幼稚的O（N）上改进的（2-ε）的完全动态算法，即使允许amortized时间结合和随机化。
对于低建立图形（例如，平面图和图形不包括固定的未成年人），我们设计了另一个简单的确定性算法，具有子词素的更新时间。 n）。
我们还显示了一种具有O（n+M）最佳空间使用情况的确定性算法，该算法对于任意图，其最大匹配度与O（√m）的摊销更新时间保持最大匹配。
A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n-vertex graphs using a trivial deterministic algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the naive O(n) one was reported up to this date. The only progress in this direction is due to Ivkovic and Lloyd [14], who in 1993 devised a deterministic algorithm with an amortized update time of O((n+m)√2/2), where m is the number of edges.
In this paper we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic worst-case update time of O(√m). Moreover, our algorithm maintains a matching which is in fact a 3/2-approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2-ε)-approximate MCM improving upon the naive O(n) was known prior to this work, even allowing amortized time bounds and randomization.
For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with sub-logarithmic update time. Specifically, it maintains a fully dynamic maximal matching with amortized update time of O(log n/log log n). This result addresses an open question of Onak and Rubinfeld [19].
We also show a deterministic algorithm with optimal space usage of O(n+m), that for arbitrary graphs maintains a maximal matching with amortized update time of O(√m).