论文标题
在实践中更快的完全动态的传递闭合
Faster Fully Dynamic Transitive Closure in Practice
论文作者
论文摘要
完全动态的传递闭合问题要求在任意顶点之间的有向图中维护可及性信息，而该图进行了一系列边缘插入和删除。该问题已经在理论上进行了彻底的研究，并且在过去几十年中提出了许多用于解决该问题的专业算法。在两项大型研究中[Frigioni EA，2001; Krommidas和Zaroliagis，2008]，许多这些算法已通过实验评估了用于图形遍历的简单静态算法，显示了实践中简单算法的竞争力甚至优势，除了非常密集的随机图或非常高的质量比率。这些研究的主要缺点是仅考虑了小且大多是随机生成的图。 在本文中，我们设计了新的算法，以维护简单且效率高的全对可及性信息。此外，我们对生成的和现实世界实例进行了广泛的实验评估，这些实例比以前的研究大几个数量级。我们的结果表明，在实践中，我们的新算法在所有类型的输入上都优于所有最新算法。
The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered. In this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.
