Papers › A Dynamic Data Structure for Temporal Reachability with Unsorted Contact Insertions
A Dynamic Data Structure for Temporal Reachability with Unsorted Contact Insertions
Luiz F. Afra Brito, Marcelo Albertini, Arnaud Casteigts, Bruno A. N. Travençolo
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Temporal graphs represent interactions between entities over the time. These interactions may be direct (a contact between two nodes at some time instant), or indirect, through sequences of contacts called temporal paths (journeys). Deciding whether an entity can reach another through a journey is useful for various applications in communication networks and epidemiology, among other fields. In this paper, we present a data structure which maintains temporal reachability information under the addition of new contacts (i.e., triplets (u,v,t) indicating that node u and node v interacted at time t). In contrast to previous works, the contacts can be inserted in arbitrary order -- in particular, non-chronologically -- which corresponds to systems where the information is collected a posteriori (e.g. when trying to reconstruct contamination chains among people). The main component of our data structure is a generalization of transitive closure called timed transitive closure (TTC), which allows us to maintain reachability information relative to all nested time intervals, without storing all these intervals, nor the journeys themselves. TTCs are of independent interest and we study a number of their general properties. Let n be the number of nodes and τ be the number of timestamps in the lifetime of the temporal graph. Our data structure answers reachability queries regarding the existence of a journey from a given node to another within given time interval in time O(logτ); it has an amortized insertion time of O(n²logτ); and it can reconstruct a valid journey that witnesses reachability in time O(klogτ), where k<n is the maximum number of edges of this journey. Finally, the space complexity of our reachability data structure is O(n²τ), which remains within the worst-case size of the temporal graph itself.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections