  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.
