We present the first data structures that maintain near optimal maximum cardinality and maximum weighted matchings on sparse graphs in sub linear time per update. Our main result is a data structure that maintains a (1+ε) approximation of maximum matching under edge insertions/deletions in worst case Õ(?mε-2) time per update. This improves the 3/2 approximation given by Neiman and Solomon [20] which runs in similar time. The result is based on two ideas. The first is to re-run a static algorithm after a chosen number of updates to ensure approximation guarantees. The second is to judiciously trim the graph to a smaller equivalent one whenever possible. We also study extensions of our approach to the weighted setting, and combine it with known frameworks to obtain arbitrary approximation ratios. For a constant ε and for graphs with edge weights between 1 and N, we design an algorithm that maintains an (1+ε) approximate maximum weighted matching in Õ(?m log N) time per update. The only previous result for maintaining weighted matchings on dynamic graphs has an approximation ratio of 4.9108, and was shown by An and et al. [2], [3].
展开▼
机译：我们介绍了第一个数据结构，该结构在每次更新的亚线性时间内在稀疏图上保持接近最佳的最大基数和最大加权匹配。我们的主要结果是一个数据结构，在每次更新的最坏情况Õ（Δm＆eps-2;）时间下，在边缘插入/删除下维持最大匹配的（1 +＆epsi;）近似值。这改善了Neiman和Solomon [20]给出的3/2近似值，它们在相似的时间运行。结果基于两个想法。首先是在选择一定数量的更新后重新运行静态算法，以确保近似保证。第二种是在可能的情况下明智地将图形修整为较小的等效图形。我们还研究了加权方法的扩展，并将其与已知框架结合以获得任意近似比率。对于恒定的＆epsi;对于边缘权重在1到N之间的图形，我们设计了一种算法，该算法在每次更新的Õ（？m log N）时间内保持（1 + eps）近似最大加权匹配。维持动态图上加权匹配的唯一先前结果是近似比为4.9108，由An and et al。给出。 [2]，[3]。
展开▼
