Dynamic Compact Data Structure for Temporal Reachability with Unsorted
Contact Insertions
Luiz Fernando Afra Brito, Marcelo Keese Albertini, Bruno Augusto Nassif
Travençolo, and Gonzalo Navarro
Temporal graphs represent interactions between entities over time. Deciding
whether entities can reach each other through temporal paths is useful for
various applications such as in communication networks and epidemiology.
Previous works have studied the scenario in which addition of new interactions
can happen at any point in time. A known strategy maintains, incrementally, a
Timed Transitive Closure by using a dynamic data structure composed of
O(n^2)binary search trees containing non-nested time intervals. However, space
usage for storing these trees grows rapidly as more interactions are inserted.
In this paper, we present a compact data structure that represents each tree
as two dynamic bit-vectors. In our experiments, we observed that our data
structure improves space usage while having similar time performance for
incremental updates when comparing with the previous strategy in temporally
dense temporal graphs.