论文标题
通过层次EDCS进行完全动态匹配的新权衡
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
论文作者
论文摘要
我们研究了完全动态图中的最大匹配问题：图形正在插入边缘插入和删除，其目标是在每个边缘更新后有效地维护较大的匹配。近年来，这个问题受到了很大的关注。已知的算法自然表现出维持匹配质量（即近似比）与每次更新所需的时间之间的权衡。尽管已经获得了几个有趣的结果，但这种权衡的最佳行为仍然在很大程度上不清楚。我们的主要贡献是一种新的方法，用于设计完全动态的近似匹配算法，该算法不仅以统一的方式（本质上）恢复了通过非常不同的技术实现的所有以前已知的权衡，而且还揭示了一些新的折衷。作为实现这一目标的主要工具，我们介绍了Bernstein和Stein（2015）的边缘限制子图（EDC）的概括，我们称为层次EDCS（HEDCS）。
We study the maximum matching problem in fully dynamic graphs: a graph is undergoing both edge insertions and deletions, and the goal is to efficiently maintain a large matching after each edge update. This problem has received considerable attention in recent years. The known algorithms naturally exhibit a trade-off between the quality of the matching maintained (i.e., the approximation ratio) and the time needed per update. While several interesting results have been obtained, the optimal behavior of this trade-off remains largely unclear. Our main contribution is a new approach to designing fully dynamic approximate matching algorithms that in a unified manner not only (essentially) recovers all previously known trade-offs that were achieved via very different techniques, but reveals some new ones as well. As our main tool to achieve this, we introduce a generalization of the edge-degree constrained subgraph (EDCS) of Bernstein and Stein (2015) that we call the hierarchical EDCS (HEDCS).
