论文标题
实践中的动态匹配算法
Dynamic Matching Algorithms in Practice
论文作者
论文摘要
近年来，在完全动态最大匹配算法的设计和分析中取得了重大进展。但是，从实际角度来看，这些理论上的结果很少受到关注。在实际数据集上实施和测试了很少的算法，其实际潜力远非理解。在本文中，我们试图弥合理论和实践之间的差距，而理论和实践目前正在观察到完全动态的最大匹配问题。我们设计了几种算法，并在一系列动态实例上凭经验研究了这些算法。
In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.
