Dynamic compact data structure for temporal reachability with unsorted contact insertions.

The article focuses on the development of a compact incremental data structure for maintaining Timed Transitive Closures (TTCs) in temporal graphs, which represent interactions between entities over time. The proposed data structure replaces the previously used |$O(n^{2})$| binary search trees (BSTs) with pairs of dynamic bit-vectors encoding non-nested time intervals, supporting key operations such as insertion and reachability queries with comparable time complexity. Two variants are introduced: a DENSE variant storing bits explicitly, which is more space-efficient for temporally dense graphs, and a SPARSE variant encoding only active bits via distances, which uses less space for temporally sparse graphs but incurs higher runtime overhead. Experimental results demonstrate that the new data structure significantly reduces space usage while maintaining similar or acceptable time performance compared to the BST-based approach, with potential for further optimization by merging bit-vectors or hybrid leaf representations.