#  A Dynamic Data Structure for Temporal Reachability
with Unsorted Contact Insertions

Luiz F. Afra Brito  Federal University of Uberlândia, Brazil  University of
Bordeaux, France  Marcelo Albertini  Federal University of Uberlândia, Brazil
Arnaud Casteigts  University of Bordeaux, France  Bruno A. N. Travençolo
Federal University of Uberlândia, Brazil

###### Abstract

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 $\tau$ 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\tau)$; it has an amortized
insertion time of $O(n^{2}\log\tau)$; and it can reconstruct a valid journey
that witnesses reachability in time $O(k\log\tau)$, where $k<n$ is the maximum
number of edges of this journey. Finally, the space complexity of our
reachability data structure is $O(n^{2}\tau)$, which remains within the worst-
case size of the temporal graph itself.

##  1 Introduction

Temporal graphs represent interactions between entities over the time. These
interactions often appear in the form of contacts at specific timestamps.
Moreover, entities can also interact indirectly with each others by chaining
several contacts over time. For example, in a communication network, devices
that are physically connected can send new messages or propagate received
ones; thus, by first sending a new message and, then, repeatedly propagating
messages over time, remote entities can communicate indirectly. Time-
respecting paths in temporal graphs are known as temporal paths, or simply
_journeys_ , and when a journey exists from one node to another node, we say
that the first can _reach_ the second.

In a computational environment, it is often useful to check whether entities
can reach each other. Investigations on temporal reachability have been used
for characterizing mobile and social networks [19]; for validating protocols
and better understanding communication networks [5, 21]; for checking the
existence of trajectories and improving flow in transportation networks [23,
22, 3]; for assessing future states of ecological networks [15]; and for
making plans for agents using automation networks [4]. Beyond the sole
reachability, some applications require the ability to reconstruct a concrete
journey if one exists. For example, journey reconstruction has been used for
finding and visualizing detailed trajectories in transportation networks [23,
9, 28, 11]; for visualizing system dynamics [12]; and for matching temporal
patterns in temporal graph databases [16, 13].

In standard graphs, the problem of maintaining reachability information under
various modifications of the graph is known as _dynamic connectivity_ and has
been extensively studied [1, 10, 7, 29, 18, 20]. Here, the adjective _dynamic_
does not refer to the temporal nature of the network, it refers to the fact
that the computed information is to be updated after the input graph is
changed. This maintenance is performed by means of a _dynamic data structure_
, which stores intermediate information to speed up the query time (and its
own update time after a change). Three types of dynamic data structures are
classically considered, depending on the type of change allowed, namely
_incremental_ (insertion only), _decremental_ (deletion only), and _fully-
dynamic_ (both). Typically, the elements to be inserted and removed in the
classical version are the edges of the graph.

In the case of temporal graphs, the elements to be inserted are not edges but
contacts, which are edges together with a timestamp, which indicates that the
two corresponding nodes interacted at this particular time. An important
aspect of data structures which manipulate contacts is whether the order of
insertion respects the order of the interactions themselves, i.e., the
insertions are _chronological_. Algorithms for updating reachability
information with the assumption that the input is chronological have been
proposed [2, 21]. However, this assumption does not capture important use
cases where the contacts are collected in an unpredictable order and the
reachability information is updated afterwards. For instance, during scenarios
of epidemics, outdated information containing the interaction details among
infected and non-infected individuals are reported in arbitrary order. Then,
this information is periodically queried in order to better understand the
dissemination process, and then take appropriate measures for reducing
reachability and identifying sources of contamination [26, 25, 8, 17].

Motivated by such scenarios, we investigate the problem of maintaining an
incremental data structure for temporal reachability, where the insertions of
contacts are made in arbitrary order. A naive approach is to store and update
the temporal graph itself (e.g., as a set of contact), then run standard
journey computation algorithms like [27] when a query is made. However, the
goal of a data structure is to reduce the computational cost of the queries
based on pre-computing intermediate information. In fact, data structures
typically offer a tradeoff between query time, update time, and space. To the
best of our knowledge, the only existing work supporting non-chronological
contact insertions and exploiting intermediate representations for speeding up
reachability queries in temporal graphs is [24]. The solution in [24] relies
on maintaining a directed acyclic graph (DAG) in which every original vertex
is possibly copied up to $\tau$ times (where $\tau$ is the number of
timestamps) and a journey exists from $u$ to $v$ in the interval
$[t,t^{\prime}]$ if and only if and vertex $u_{t}$ can reach vertex
$v_{t^{\prime}}$ in the DAG. Some paths preprocessing is additionally
considered that results in an average speed up for reachability queries.
However, the worst-case query time corresponds to a standard path search (e.g.
depth first search) in the DAG, which takes $\Theta(n^{2}\tau)$ time in the
case of dense temporal graphs (whose number of contacts is of the same order).
The space complexity (size of the DAG) also corresponds essentially to the
number of contacts, thus $\Theta(n^{2}\tau)$ in the worst case. Finally, the
update time upon insertion is quite efficient, because the DAG representation
allows its effect to remain local. If one ignores the cost of paths
preprocessing in [24] (as we focus on worst-case analysis), it only takes
$O(1)$ time to update the DAG if the corresponding nodes are already known,
and up to $\Theta(\tau)$ otherwise, due to the creation of (up to) $\tau$
copies of the new nodes.

###  1.1 A data structure for unsorted contact insertions

In this paper, we consider the problem of maintaining reachability information
through a data structure111We have a simple implementation available at
https://github.com/albertiniufu/dynamictemporalgraph/ that supports the
following four operations, where by convention, $\mathcal{G}$ is a temporal
graph, $u$ and $v$ are vertices of $\mathcal{G}$, and $t,t_{1},$ and $t_{2}$
are timestamps:

  * •

add_contact(u, v, t): Update information based on a contact from $u$ to $v$ at
time $t$

  * •

can_reach(u, v, $t_{1}$, $t_{2}$): Return true if $u$ can reach $v$ within the
interval $[t_{1},t_{2}]$

  * •

is_connected($t_{1}$, $t_{2}$): Return true if $\mathcal{G}$ restricted to the
interval $[t_{1},t_{2}]$ is temporally connected, i.e. all vertices can reach
each other within the interval $[t_{1},t_{2}]$

  * •

reconstruct_journey(u, v, $t_{1}$, $t_{2}$): Return a journey (if one exists)
from $u$ to $v$ occurring within the interval $[t_{1},t_{2}]$

For generality, we consider directed contacts (timed arcs). Furthermore, if
$t_{1}$ and $t_{2}$ are omitted in the above operations, then the entire
lifetime of $\mathcal{G}$ is considered. The challenge in realizing these
operations is to answer queries as fast as possible, while keeping space
consumption and update time at reasonable levels. The worst-case complexities
are as follows: the query operations, can_reach(u, v, $t_{1}$, $t_{2}$) and
is_connected($t_{1}$, $t_{2}$), run, respectively, in $O(\log\tau)$ and
$O(n^{2}\log\tau)$ time; the update operation, add_contact(u, v, t), runs in
$O(n^{2}\log\tau)$ amortized time; and the retrieval operation,
reconstruct_journey(u, v, $t_{1}$, $t_{2}$), runs in $O(k\log\tau)$ time,
where $k<n$ is the length of the resulting journey. The worst-case space
complexity remains within the worst-case size of the temporal graph itself,
namely $O(n^{2}\tau)$. Overall, the space complexity is comparable to that of
[24], while the query time is much faster and the update time is slower.

The core of our data structure is a component called the _timed transitive
closure_ (TTC), which generalizes the classical notion of a transitive closure
(TC). Classical TCs capture reachability information among vertices over the
entire lifetime of the network. They are classically encoded as a static
directed graph where the existence of an arc from $u$ to $v$ implies that
there is a journey $u$ to $v$ in the temporal graph. If one is not interested
in querying reachability for specific subintervals, and if the contacts are
inserted in chronological order, then TCs are actually sufficient for
maintaining temporal reachability information (see e.g. [2]). A generalization
of TC has also been considered in [21], which allows queries to be
parametrized by a maximum journey duration, however basic journey information,
such as departure and arrival times, are not known and the computation of the
structure requires the information to be processed at once and chronologically
(i.e. subsequent updates are not supported).

In the unsorted (i.e., non-chronological) case, TCs do not provide enough
information to decide whether a new contact (possibly occurring at any point
in history) can be composed with known journeys. To address this need, we
introduce a generalization of TCs called _timed transitive closure_ (TTCs),
which store information regarding the availability of journeys for a well-
chosen set of time intervals, without storing the journeys themselves. We
study the general properties of TTCs and we prove, in particular, that one can
restrict the number of intervals considered to $O(\tau)$ for any pair of nodes
(as opposed to $O(\tau^{2})$), with immediate consequences on the space
complexity of a data structure based on TTCs. This information is then
exploited by our data structure algorithms.

###  1.2 Organization of the document

This paper is organized as follows. In Section 2, we present basic
definitions. In Section 3, we introduce timed transitive closures, study their
basic properties, and provide a number of low-level primitives for
manipulating them. In Section 4, we describe the algorithms that perform each
operation of our data structure based on TTCs, together with their running
time complexities. Finally, Section 5 concludes with some remarks and open
questions.

##  2 Definitions

Following the formalism in [6], a temporal graph can be generally represented
by a tuple $\mathcal{G}=(V,E,\mathcal{T},\rho,\zeta)$, where $V$ is a set of
vertices, $E\subseteq{}V\times V$ is a set of edges, $\mathcal{T}$ is the time
interval over which the network exists (_lifetime_),
$\rho:E\times\mathcal{T}\to\\{0,1\\}$ is a _presence function_ that expresses
whether a given edge is present at a given time instant, and
$\zeta:E\times\mathcal{T}\mapsto\mathbb{T}$ is a latency function that
expresses the duration of an interaction for a given edge at a given time,
where $\mathbb{T}$ is the time domain (typically $\mathbb{R}$ or
$\mathbb{N}$). In this paper, we consider a setting where $E$ is a set of arcs
(directed edges), $\mathbb{T}$ is equal to $\mathbb{N}$ (time is discrete) and
$\mathcal{T}=[1,\tau]\subseteq\mathbb{T}$ (the lifetime contains $\tau$
timestamps). The latency function is constant, namely $\zeta=\delta$, where
$\delta$ is any fixed positive integer (typically $0$ or $1$). We call
$(u,v,t)$ a _contact_ in ${\mathcal{G}}$ if $\rho((u,v),t)=1$. We use a short-
hand notation $\mathcal{G}_{[t_{1},t_{k}]}$ when restricting the lifetime of
${\mathcal{G}}$ to a subinterval $[t_{1},t_{k}]\subseteq\mathcal{T}$, and call
$\mathcal{G}_{[t_{1},t_{k}]}$ a temporal subgraph of $\mathcal{G}$. Finally,
the static graph $G=(V,E)$ is called the _underlying graph_ of $\mathcal{G}$.

Reachability in temporal graphs is defined in a time-respecting way, by
requiring that a path travels along increasing times (resp. non-decreasing
times) if $\delta\geq 1$ (resp. if $\delta=0$). These paths are called
temporal paths or journeys, interchangeably.

######  Definition 1 (Journey).

A journey from $u$ to $v$ in $\mathcal{G}$ is a sequence of contacts
$\mathcal{J}=\langle c_{1},c_{2},\ldots,c_{k}\rangle$, whose sequence of
underlying arcs form a valid $(u,v)$-path in the underlying graph $G$ and for
each contact $c_{i}=(u_{i},v_{i},t_{i})$, it holds that
$\rho((u_{i},v_{i}),t_{i})=1$ and $t_{i+1}\geq t_{i}+\delta$ for each
$i\in[1,k-1]$. Additionally, we say that $departure(\mathcal{J})=t_{1}$,
$arrival(\mathcal{J})=t_{k}+\delta$ and
$duration(\mathcal{J})=arrival(\mathcal{J})-departure(\mathcal{J})$.

A journey is _trivial_ if it consists of a single contact.

######  Definition 2 (Reachability).

A vertex $u$ can _reach_ a vertex $v$ within time interval $[t_{1},t_{2}]$ iff
there exists a journey $\mathcal{J}$ from $u$ to $v$ in
$\mathcal{G}_{[t_{1},t_{2}]}$ (i.e., such that $departure(\mathcal{J})\geq
t_{1}$ and $arrival(\mathcal{J})\leq t_{2}$).

The (standard) _transitive closure_ (TC) of a temporal graph $\mathcal{G}$ is
a static directed graph $\mathcal{G}^{*}=(V,E^{*})$ such that $(u,v)\in E^{*}$
if and only if $u$ can reach $v$ in $\mathcal{G}$. This notion is illustrated
in Figure 1. As already explained, if the contacts are discovered in a
chronological order, then $\mathcal{G}^{*}$ can be updated incrementally to
compute the entire reachability information of $\mathcal{G}$ [2]. In the
unsorted case, however, this notion is not sufficient because it does not
allows one to decide if a new contact can be composed with previously-known
journeys, which motivates the definition of more powerful objects.

$a$$b$$c$$d$$2$$4$$1$$4$$4$$5$

$a$$b$$c$$d$

Figure 1:  (Left) A temporal graph $\mathcal{G}$ on four vertices
$V=\\{a,b,c,d\\}$, where the presence times of the arcs are depicted by
labels. Whether $\delta=0$ or $1$, this graph has only two non-trivial
journeys, namely $\mathcal{J}_{1}=\langle(a,b,2),(b,d,4)\rangle$ and
$\mathcal{J}_{2}=\langle(a,c,4),(c,d,5)\rangle$. (Right) Transitive closure
$\mathcal{G}^{*}$. Note that $\mathcal{J}_{1}$ and $\mathcal{J}_{2}$ are
represented by the same arc in $\mathcal{G}^{*}$ (the two contacts from $b$ to
$d$ as well).

##  3 Reachability tuples and Timed Transitive Closure

In this section, we describe an extension of the concept of transitive closure
called _timed transitive closure_ (TTC). The purpose of TTCs is to encode
reachability information among the vertices, parametrized by time intervals,
so that one can subsequently decide if a new contact occurring anywhere in
history can be composed with existing journeys. The main components of TTCs
are called _reachability tuples_ (R-tuples). We introduce a number of
operators on R-tuples, such as inclusion and concatenation, and describe their
role in the construction and maintenance of a TTC.

###  3.1 Reachability tuples (R-tuples)

Just as the number of paths in a static graph, the number of journeys in a
temporal graph could be too large to be stored explicitly (typically,
factorial in $n$). To avoid this problem, R-tuples capture the fact that a
node can reach another within a certain time interval without storing the
corresponding journeys. Thus, a single R-tuple may capture the reachability
information corresponding to many possible journeys. We distinguish between
two versions of R-tuples, namely (_existential_) R-tuples and _constructive_
R-tuples, the latter adding information for reconstructing a journey that
witnesses reachability.

####  3.1.1 Existential R-tuples

The following definitions are given in the context of a temporal graph
$\mathcal{G}$ whose vertex set is $V$, lifetime is $\mathcal{T}=[1,\tau]$, and
latency is $\delta$.

######  Definition 3 (R-tuple).

An (existential) R-tuple is a quadruplet $r=(u,v,t^{-},t^{+})$, where $u$ and
$v$ are vertices in $\mathcal{G}$, and $t^{-}$ and $t^{+}$ are timestamps in
$\mathcal{T}$. It encodes the fact that node $u$ can reach node $v$ through a
journey $\mathcal{J}$ such that $departure(\mathcal{J})=t^{-}$ and
$arrival(\mathcal{J})=t^{+}$. If several such journeys exist, then they are
all captured by the same R-tuple.

The set of journeys captured by an R-tuple $r$ is denoted by $\mathcal{J}(r)$,
and we say that $r$ _represents_ these journeys. An R-tuple is _trivial_ when
it represents a trivial journey (i.e., a single contact). Trivial R-tuples
thus have the form $(u,v,t,t+\delta)$ for some $t$. The following relations
and operations are quite natural to define.

######  Definition 4 (Precedence $\prec$).

An interval $I_{1}=[t^{-}_{1},t^{+}_{1}]$ precedes an interval
$I_{2}=[t^{-}_{2},t^{+}_{2}]$, noted $I_{1}\prec I_{2}$, if
$t^{+}_{1}\leq{}t^{-}_{2}$. Given two R-tuples
$r_{1}=(u_{1},v_{1},t^{-}_{1},t^{+}_{1})$ and
$r_{2}=(u_{2},v_{2},t^{-}_{2},t^{+}_{2})$, $r_{1}$ precedes $r_{2}$, noted
$r_{1}\prec{}r_{2}$ if $t^{+}_{1}\leq{}t^{-}_{2}$ and $u_{2}=v_{1}$.

Intuitively, the precedence relation among R-tuples tells us that the journeys
they represent can be composed, leading to another R-tuple as follows:

######  Definition 5 (Concatenation $\cdot$).

Given two R-tuples $r_{1}=(u_{1},v_{1},t^{-}_{1},t^{+}_{1})$ and
$r_{2}=(u_{2},v_{2},t^{-}_{2},t^{+}_{2})$ such that $r_{1}\prec{}r_{2}$, the
concatenation of $r_{1}$ with $r_{2}$ is the R-tuple $r_{1}\cdot
r_{2}=(u_{1},v_{2},t^{-}_{1},t^{+}_{2})$.

The natural inclusion among intervals extends to R-tuples as follows:

######  Definition 6 (Inclusion $\subseteq$).

Given two R-tuples $r_{1}=(u_{1},v_{1},t^{-}_{1},t^{+}_{1})$ and
$r_{2}=(u_{2},v_{2},t^{-}_{2},t^{+}_{2})$, $r_{1}\subseteq{}r_{2}$ if and only
if $u_{1}=u_{2}$, $v_{1}=v_{2}$, and
$[t^{-}_{1},t^{+}_{1}]\subseteq[t^{-}_{2},t^{+}_{2}]$ (that is,
$t^{-}_{2}\leq{}t^{-}_{1}\leq{}t^{+}_{1}\leq{}t^{+}_{2}$).

If neither $r_{1}\subseteq r_{2}$ nor $r_{2}\subseteq r_{1}$ (or if the
vertices are different), then $r_{1}$ and $r_{2}$ are called _incomparable_.
Intuitively, if $r_{1}\subseteq r_{2}$, then any of the journeys represented
by $r_{2}$ could be replaced by a (possibly faster) journey represented by
$r_{1}$. More precisely:

######  Lemma 1.

Let $u$ and $v$ be two nodes in $V$. Let
$\mathcal{I}_{1}=[t_{1}^{-},t_{1}^{+}]$ and
$\mathcal{I}_{2}=[t_{2}^{-},t_{2}^{+}]$ be two subintervals of $\mathcal{T}$
such that $\mathcal{I}_{1}\subseteq\mathcal{I}_{2}$. If $u$ can reach $v$
within $\mathcal{I}_{1}$, then $u$ can reach $v$ within $\mathcal{I}_{2}$.

###### Proof.

The proof is straightforward, we give it for completeness. Let $r$ be the
R-tuple $(u,v,t_{1}^{-},t_{1}^{+})$ and let $\mathcal{J}$ be any of the
journeys in $\mathcal{J}(r)$. One can reach $v$ from $u$ within
$\mathcal{I}_{2}$ through the three following steps: (1) wait at $u$ from
$t_{2}^{-}$ to $t_{1}^{-}$, (2) travel from $u$ to $v$ using $\mathcal{J}$,
and finally (3) wait at $v$ from $t_{1}^{+}$ to $t_{2}^{+}$. ∎

The main consequence of Lemma 1 is that if $r_{1}\subseteq r_{2}$, then
$r_{2}$ is redundant for answering reachability queries from $u$ to $v$.

######  Definition 7 (Redundancy).

Let $S$ be a set of R-tuples and let $r\in S$, $r$ is called _redundant_ in
$S$ if there exists $r^{\prime}\in S$ such that $r^{\prime}\subseteq r$. A set
with no redundant R-tuple is called _irredundant_.

An R-tuple that is non-redundant in a set is also called _minimal_ (in that
set). It is natural to ask what the maximum size of an _irredundant_ set of
R-tuples could be, with consequences for the space complexity of a
reachability data structure based on R-tuples. It turns out that this number
is always significantly smaller than the number of possible R-tuples.

######  Lemma 2.

The maximum size of an irredundant set of R-tuples for $\mathcal{G}$ is
$\Theta(n^{2}\tau)$.

###### Proof.

First, we prove that the maximum number of pairwise incomparable R-tuples is
$O(n^{2}\tau)$. Then, we show that this bound is tight, as some graphs induce
$\Theta(n^{2}\tau)$ incomparable R-tuples.
(1) Upper bound: There are $\Theta(n^{2})$ ordered pairs of vertices. Thus, it
is sufficient to show that for each pair $(u,v)$, the number of incomparable
R-tuples whose starting vertex is $u$ and whose ending vertex is $v$ is
$\Theta(\tau)$. Let $S$ be an irredundant set of such R-tuples, and let
$r_{1}=(u,v,t_{1}^{-},t_{1}^{+})$ and $r_{2}=(u,v,t_{2}^{-},t_{2}^{+})$ be any
two R-tuples in $S$. If $t^{-}_{1}=t^{-}_{2}$, then either $r_{1}\subseteq
r_{2}$ or $r_{2}\subseteq r_{1}$, thus $S$ is redundant (contradiction). As a
result, all departure timestamps $t^{-}_{i}$ belonging to the R-tuples in $S$
are different, which implies that $|S|\leq\tau$.
(2) Tightness: Consider the complete temporal graph $\mathcal{K}_{n,\tau}$ on
$n$ vertices in which every edge is present in _all_ timestamps in $[1,\tau]$.
In such a graph, there are consequently $\Theta(n^{2}\tau)$ contacts, each of
which is a trivial journey. Now, observe that either these journeys connect
different vertices, or their intervals are incomparable (same duration with
different starting times), thus none of them is redundant with the others. ∎

Given a graph $\mathcal{G}$ and a set $S$ of R-tuples representing all the
journeys of $\mathcal{G}$, the subset $S^{\prime}\subseteq S$ of all minimal
R-tuples is called the _representative_ R-tuples of $\mathcal{G}$, denoted by
$\mathcal{R}(\mathcal{G})$. We also write $\mathcal{R}(u,v)$ for those
R-tuples in $\mathcal{R}(\mathcal{G})$ whose source is $u$ and destination is
$v$. From the proof of Lemma 2, we extract:

######  Observation 1.

Every contact of $\mathcal{G}$ is present in $\mathcal{R}(\mathcal{G})$ in the
form of a trivial R-tuple.

Observation 1 implies that $\mathcal{R}(\mathcal{G})$ is a _non-lossy_
representation, as $\mathcal{G}$ itself is contained in it. The down side is
that its space complexity is at least as large as the number of contacts in
$\mathcal{G}$. Observe that, up to a constant factor, it can however not be
worse than the worst number of contacts, since there may exist up to
$\Theta(n^{2}\tau)$ contacts and irredundant sets cannot exceed this size
(Lemma 2). In other words, in dense temporal graphs, the reachability
information offered by R-tuples is essentially free in space.

####  3.1.2 Constructive R-tuples

The data structure considered in this work has four operations, namely
add_contact, can_reach, is_connected, and reconstruct_journey. The first three
operations can be dealt with using only existential R-tuple. The fourth
operation could benefit from storing a small amount of additional information
into the R-tuple.

######  Definition 8 (Constructive R-tuple).

A constructive R-tuple $r=(u,v,t^{-},t^{+},w)$ contains the same information
as an existential R-tuple, plus a vertex $w$ such that at least one journey
$\mathcal{J}\in\mathcal{J}(r)$ starts with the contact $(u,w,t^{-})$. Node $w$
is called the _successor_ of $u$ in $r$ (resp., in $\mathcal{J}$).

Most of the definitions and lemmas from Section 3.1 apply unchanged to
constructive R-tuple. In particular, the definition of redundant R-tuples
applies without considering the successor field. Indeed, if two constructive
R-tuples differ only by the successor node, then they are seen as equivalent
and any of the two can be discarded. As for the concatenation of two
constructive R-tuples $r_{1}=(u_{1},v_{1},t^{-}_{1},t^{+}_{1},w_{1})$ and
$r_{2}=(u_{2},v_{2},t^{-}_{2},t^{+}_{2},w_{2})$, provided $r_{1}\prec r_{2}$,
we additionally require that the resulting R-tuple adopts the successor of
$r_{1}$ as its own successor; that is, $r_{1}\cdot
r_{2}=(u_{1},v_{2},t^{-}_{1},t^{+}_{2},w_{1})$. For simplicity, whenever
constructive R-tuples are not needed, we describe the algorithms using
existential R-tuples.

###  3.2 Timed Transitive Closure

Informally, the timed transitive closure of a temporal graph $\mathcal{G}$ is
a multigraph that captures the existence of journeys within all possible time
intervals, based on irredundant R-tuples.

######  Definition 9 (Timed transitive closure).

Given a graph $\mathcal{G}$, the _timed transitive closure_ of $\mathcal{G}$,
noted $TTC(\mathcal{G})$, is a (static) directed multigraph on the same set of
vertices, whose arcs correspond to the representative R-tuples of
$\mathcal{G}$.

$a$$b$$c$$d$$[2,3]$$[4,5]$$[1,2]$$[4,5]$$[4,5]$$[5,6]$$[2,5]$$[4,6]$

$a$$b$$c$$d$$([2,3],b)$$([4,5],d)$$([1,2],d)$$([4,5],c)$$([4,5],a)$$([5,6],d)$$([2,5],b)$$([4,6],c)$

Figure 2: Timed transitive closure ${\footnotesize TTC}(\mathcal{G})$ of the
temporal graph $\mathcal{G}$ in Figure 1, considering $\delta=1$. On the left,
the version with existential R-tuple, whose intervals are depicted by labels.
On the right, the version with constructive R-tuples, depicting also the
successor.

Figure 2 shows two examples of TTCs, both corresponding to the temporal graph
of Figure 1 (one for existential R-tuples, the other for constructive
R-tuples). Algorithmically, a TTC provides most of the support needed to
realize the high-level operations of our data structure. For example, the
operation can_reach(u, v, $t_{1}$, $t_{2}$) amounts to testing if there exists
an arc whose associated R-tuple is $(u,v,t^{-},t^{+})$ with
$[t^{-},t^{+}]\subseteq[t_{1},t_{2}]$. The operation is_connected($t_{1}$,
$t_{2}$) can be realized by performing such a test for every pair of vertices.
The operation add_contact(u, v, t) reduces to adding a new arc to the
TTC($\mathcal{G}$) if no smaller interval already captures this information.
If the new arc is added, then some other arcs may become redundant and should
be removed, some others may also be created by composition. This operation is
therefore the most critical. Finally, if constructive R-tuples are used, then
an actual journey may be reconstructed quite efficiently from
TTC($\mathcal{G}$) when reconstruct_journey(u, v, $t_{1}$, $t_{2}$) is called,
by retrieving a constructive R-tuple $(u,v,t^{-},t^{+},w)$ such that
$[t^{-},t^{+}]\subseteq[t_{1},t_{2}]$ and unfolding the corresponding journey
inductively, by replacing $u$ with the successor vertex $w$ and $t^{-}$ with
$t^{-}+\delta$ in each step.

All algorithms for these operations are described in Section 4. Before doing
so, we present an explicit encoding of TTCs based on adjacency matrices and
binary search trees (BST). In order for the high-level algorithms to remain
independent from this particular choice, we define a set of primitives for
manipulating the TTC, that are used by the high-level algorithms of Section 4.

####  3.2.1 Encoding the TTC

We encode the TTC by an $n\times n$ matrix, in which every entry $(i,j)$
points to a self-balanced binary search tree (BST) denoted by $T(i,j)$. The
nodes in this tree contain all the time intervals corresponding to R-tuples in
$\mathcal{R}(i,j)$. From Lemma 2, we know that a tree $T(u,v)$ contains up to
$\tau$ nodes. In addition, all these intervals are incomparable, thus one can
use any of their boundaries (departure or arrival) as the sorting key of the
BST. Note that retrieving $T(u,v)$ within the matrix takes constant time, as
the cells of a matrix are directly accessed. Also recall that finding the
largest key below (resp. the smallest key above) a certain value takes
$O(\log{\tau})$ time. Similarly, inserting a new element (in our case, an
interval) takes $O(\log\tau)$ time. Finally, observe that several types of BST
(e.g. red-black trees) can self-balance without impacting the asymptotic cost
of insertions.

We provide the following low-level operations for manipulating TTCs: (1)
find_next($u,v,t$) returns the containing the earliest interval
$[t^{-},t^{+}]$ in $T(u,v)$ such that $t^{-}\geq t$, if any, and nil
otherwise; symmetrically, (2) find_previous($u,v,t$) returns the node
containing the latest interval $[t^{-},t^{+}]$ in $T(u,v)$ such that
$t^{+}\leq t$, if any, and nil otherwise; finally, (3)
insert($u,v,t^{-},t^{+}$) inserts a new node containing the interval
$[t^{-},t^{+}]$ in $T(u,v)$ and performs some operations for maintaining the
property that all intervals in $T(u,v)$ are minimal.

Let us now describe the algorithms that perform these operations, along with
their time complexities. The algorithm for find_next($u,v,t$) searches
$T(u,v)$ recursively, by comparing $t$ with the departure $t^{-}$ of the
current node interval $[t^{-},t^{+}]$. If $t^{-}$ is equals to or greater than
$t$, then the current node is a candidate answer. The algorithm then compares
the current node candidate and the previous one, and keeps the one containing
the smallest (earliest) $t^{-}$, then it descends the left child. Otherwise,
if $t^{-}$ is smaller than $t$, it simply descends the right child. As soon as
a leaf is reached (and visited), the algorithm returns the current candidate
as the answer. The algorithm for find_previous($u,v,t$) works symmetrically.
The time complexities of both algorithms correspond to the depth of the tree,
which is $O(\log{\tau})$.

$\mathcal{I}$$\mathcal{I}_{1}$$\mathcal{I}_{2}$ (a) Find

$\mathcal{I}$ (b) Remove

$\mathcal{I}$$\mathcal{I}$ (c) Insert

Figure 3: Basic steps to perform $\textsc{insert}(u,v,\mathcal{I})$ where
$\mathcal{I}=[t_{1},t_{2}]$. First, in (a), an algorithm must find the
candidate intervals that could become redundant after the inserting
$\mathcal{I}$. These intervals are exactly the ones between
$\mathcal{I}_{1}=\textsc{find\mathunderscore{}previous}(u,v,t^{+})$ and
$\mathcal{I}_{2}=\textsc{find\mathunderscore{}next}(u,v,t^{-})$. Note that
there are cases in which $\mathcal{I}_{1}$ or $\mathcal{I}_{2}$ do not exist.
Next, in (b), all intervals $\mathcal{I}^{\prime}$ between (and including)
$\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ such that
$\mathcal{I}^{\prime}\subseteq\mathcal{I}$ must be removed. Finally, in (c),
the algorithm inserts $\mathcal{I}$ in the correct place.

The algorithm for insert($u,v,t^{-},t^{+}$) finds and removes any potential
node with interval $\mathcal{I}_{i}$ such that
$[t^{-},t^{+}]\subseteq\mathcal{I}_{i}$, then it inserts a new node containing
$[t^{-},t^{+}]$ using a standard BST insertion. Figure 3 gives a linear
representation of the intervals in $T(u,v)$ while performing this operation. A
naive implementation of this operation would consist of searching and removing
each corresponding node independently. However, this would lead to a
complexity of $O(d\log\tau)$ time, where $d$ is the number of nodes removed,
that is up to $O(\tau)$. We use a non-standard approach that makes it feasible
in $O(d+\log\tau)$ time only. The strategy is to identify in $T(u,v)$ the
nodes containing, respectively, the boundary intervals
$\mathcal{I}_{1}=\textsc{find\mathunderscore{}previous}(u,v,t^{+})$ and
$\mathcal{I}_{2}=\textsc{find\mathunderscore{}next}(u,v,t^{-})$, which
correspond to the first and last nodes to be removed (note that the parameters
are indeed $t^{+}$ and $t^{-}$, not the reverse). Then, every node containing
intervals in this range is removed using the technique outlined in the proof
of Lemma 3.

######  Lemma 3.

In the worst case, the cost of the insert operation is $O(d+\log{\tau})$,
where $d$ is the number of elements removed from $T(u,v)$. The amortized cost
of an insertion is $O(\log{\tau})$.

###### Proof.

The range of intervals to be removed is characterized by two boundary
intervals $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$, which can be found by
calling both find_next and find_previous a single time, which takes
$O(\log\tau)$ time. The final insertion of the input interval in the BST also
takes $O(\log\tau)$. The difficult part is thus the removal of redundant
intervals prior to this insertion (illustrated in Figure 3). Let $d$ be the
number of intervals in the deletion range. We start by recalling the main
ideas of range deletion in a BST (see [14] for a pedagogical explanation),
then we discuss their use in the particular case of balanced BSTs, and finally
we explain why the claimed cost is correct despite the fact that balance may
be lost after the deletion. Let $\mathcal{I}_{A}$ be the common ancestor of
$\mathcal{I}_{1}$ and of $\mathcal{I}_{2}$ (possibly equal to one of these).
The process can be split into two phases, the first one is to walk upward from
$\mathcal{I}_{1}$ to $\mathcal{I}_{A}$ and the second is to walk upward
(again) from $\mathcal{I}_{2}$ to $\mathcal{I}_{A}$. As either walk proceeds,
potential deletions are performed in intermediate tree nodes. Some of these
deletions remove the node itself, replacing it by one of its child in constant
time. The intermediate branches are cut without being explored. The final cost
of $O(d+\log\tau)$ actually follows from the cumulated length of both walks.
The down side with this technique (which may explain why it is not standard in
balanced BSTs) is that the resulting tree may have lost its balance if most of
the nodes are deleted. However, as the depth cannot increase, and as we only
need that it remains of $O(\log\tau)$ for subsequent use of the tree, the
solution is good enough for our needs. Finally, observe that the number of
intervals removed cannot exceed the number of intervals previously inserted,
which is why the amortized cost of an insertion remains of $O(\log{\tau})$. ∎

Additionally, we define the following basic operations:

  * •

$\mathcal{N}^{*}_{out}(u)$ : Returns the set of vertices
$\\{v_{1},v_{2},\ldots,v_{k}\\}$ such that there exists at least one arc from
$u$ to $v_{i}$ in the TTC

  * •

$\mathcal{N}^{*}_{in}(u)$ : Returns the set of vertices
$\\{v_{1},v_{2},\ldots,v_{l}\\}$ such that there exists at least one arc from
$v_{i}$ to $u$ in the TTC

Both operations can be realized in $O(n)$ time, through traversing the
corresponding row (resp. column) of the matrix and testing if the
corresponding tree is empty.

##  4 The four operations

In this section, we describe the algorithms which perform the four operations
of our data structure, previously described in Section 1.1. These operations
are can_reach(u, v, $t_{1}$, $t_{2}$), is_connected($t_{1}$, $t_{2}$),
add_contact(u, v, t), and (optionally) reconstruct_journey(u, v, $t_{1}$,
$t_{2}$). For simplicity, the first three algorithms are presented using
existential R-tuples only (however they are straightforwardly adaptable to
constructive R-tuples). All the algorithms rely on the primitives defined in
Section 3.2.1 for manipulating the TTC in an abstract way.

###  4.1 Reachability and connectivity queries

The algorithm for performing can_reach(u, v, $t_{1}$, $t_{2}$) is
straightforward. It consists of testing whether $T(u,v)$ contains at least one
interval that is included in $[t_{1},t_{2}]$. This can be done by retrieving
$[t^{-},t^{+}]=\textsc{find\mathunderscore{}next}(u,v,t_{1})$ and checking
that $t^{+}\leq t_{2}$. Therefore, the cost of this algorithm reduces
essentially to that of the operation find_next($u,v,t_{1}$), which takes
$O(\log\tau)$ time. We note that, if $[t_{1},t_{2}]=\mathcal{T}$, then it is
sufficient to verify (in constant time) that $T(u,v)$ is not empty. Regarding
the operation is_connected($t_{1}$, $t_{2}$), a simple way of answering it is
to call can_reach(u, v, $t_{1}$, $t_{2}$) for every pair of vertices, with a
resulting time complexity of $O(n^{2}\log{\tau})$. It seems plausible that
this strategy is not optimal and could be improved in the future.

###  4.2 Update operation

The algorithm for add_contact(u, v, t) manages the insertion of a new contact
$(u,v,t)$ in the data structure, where $(u,v)\in{E}$ and $t\in{\tau}$. To
start, the interval corresponding to the trivial journey from $u$ to $v$ over
$[t,t+\delta]$ is inserted in $T(u,v)$ using the insert primitive. (Recall
that this primitive encapsulate the removal of redundant intervals in
$T(u,v)$, if any.) Then, the core of the algorithm consists of computing the
indirect consequences of this insertion for the other vertices. Namely, if a
vertex $w^{-}$ could reach $u$ before time $t$ with latest departure $t^{-}$
and $v$ could reach another vertex $w^{+}$ after time $t+\delta$ with earliest
arrival $t^{+}$, it follows that $w^{-}$ can now reach $w^{+}$ over interval
$[t^{-},t^{+}]$. Our algorithm consists of enumerating these compositions and
inserting them in the TTC. Interestingly, for each predecessor $w^{-}$ of $u$,
only the _latest_ interval ending before $t$ in $T(w^{-},u)$ needs to be
considered. The reason is that in order to compose an earlier journey
$\mathcal{J}$ with the new contact, we need to wait at $u$ until time $t$.
Thus, even though some other journeys started earlier, it would have to wait
at $u$ and it would thus eventually arrive at the same time (based on a non-
minimal interval). Based on this property, our algorithm only searches for the
latest interval preceding $t$ for each predecessor of $u$ and the earliest
interval exceeding $t+\delta$ for each successor of $v$.

The details are given in Algorithm 1, whose behavior is as follows. In Line 1,
the algorithm inserts the interval $[t,t+\delta]$ into $T(u,v)$, which
corresponds to the trivial journey induced by the new contact. In Lines 2 to
7, for every vertex $w^{-}\in\mathcal{N}^{*}_{in}(u)$, it finds the latest
interval $[t^{-},\\_]$ in $T(w^{-},u)$ that arrives before time $t$
(inclusive) and inserts the composition $[t^{-},t+\delta]$ into $T(w^{-},v)$.
For the same reasons as above, the algorithm only needs considering inserting
$[t^{-},t+\delta]$ because every other possible composition would contain it
as a subinterval. In Lines 8 to 11, for every vertex
$w^{+}\in\mathcal{N}^{*}_{out}(v)$, the algorithm finds the earliest interval
$[\,\\_\,,t^{+}]$ in $T(v,w^{+})$ that leaves $v$ after time $t+\delta$
(inclusive), and inserts the composition $[t,t^{+}]$ into $T(u,w)$. In the
same way, every other possible composition would contain $[t,t^{+}]$ as a
subinterval. Finally, in Lines 12 to 14, for all
$w^{-}\in\mathcal{N}^{*}_{in}(u)$ and $w^{+}\in\mathcal{N}^{*}_{out}(v)$, it
inserts the composition $[t^{-},t^{+}]$ into $T(w^{-},w^{+})$. In order to
optimize this last step, the algorithm only considers the subset of
$\mathcal{N}^{*}_{in}$ whose reachability to $v$ has been impacted by the new
contact, thanks to a dedicated storage $D$ computed in Line 7.

Algorithm 1 add_contact(u, v, t)

1:$t\in{\mathcal{T}},u,v\in V$ with $u\neq{}v$

2:$\textsc{insert}(u,v,t,t+\delta)$

3:$D\leftarrow{}\\{\\}$

4:for all $w^{-}\in{\mathcal{N}^{*}_{in}(u)}$ do

5: $[t^{-},\\_]\leftarrow{}\textsc{find\mathunderscore{}previous}(w^{-},u,t)$

6: if $t^{-}\neq nil$ then

7: $\textsc{insert}(w^{-},v,t^{-},t+\delta)$

8: $D\leftarrow{}D\cup{}(w^{-},t^{-})$

9:for all $w^{+}\in{\mathcal{N}^{*}_{out}(v)}$ do

10:
$[\\_\,,t^{+}]\leftarrow{}\textsc{find\mathunderscore{}next}(v,w^{+},t+\delta)$

11: if $t^{+}\neq nil$ then

12: $\textsc{insert}(u,w^{+},t,t^{+})$

13: for all $(w^{-},t^{-})\in{D}$ do

14: if $w^{-}\neq w^{+}$ then

15: $\textsc{insert}(w^{-},w^{+},t^{-},t^{+})$

######  Theorem 4.

The update operation has amortized time complexity $O(n^{2}\log\tau)$. In the
worst case, a single update operation costs $O(n^{2}\tau)$ time.

###### Proof.

An insert operation is performed in Line 1. The loop from Line 3 to 7 iterates
over $O(n)$ vertices and makes at most one insertion for each. The loop from
Line 8 to 14 iterates over $O(n)$ vertices, and for each one, iterates in a
nested way over $O(n)$ vertices. For each resulting pair, it performs at most
one insert operation. The latter clearly dominates the overall cost of the
algorithm, with a cost of $O(n^{2})$ times the cost of the insert operation,
the latter being of amortized time $O(\log\tau)$ and otherwise of
$O(d+\log\tau)$ time (Lemma 3), with $d=O(\tau)$ in the worst case. ∎

###  4.3 Journey reconstruction

The algorithm for the operation reconstruct_journey(u, v, $t_{1}$, $t_{2}$)
reconstructs a journey from vertex $u$ to vertex $v$ whose contact timestamps
must be contained in $[t_{1},t_{2}]$. As explained in Section 3.1.2,
existential R-tuples can be augmented by a _successor_ field that indicates
which vertex comes next in (at least one of) the journeys represented by the
R-tuple. This information is very useful for reconstruction and has a
negligible cost (asymptotically speaking). Concretely, one can make the nodes
of the BST store the successor field in addition to the interval. The low-
level operations for manipulating the TTC (see Section 3.2.1) are unaffected,
neither are the query and update algorithms in a significant way. The only
subtlety is that when two intervals (nodes) are composed, the successor field
of the resulting node corresponds to the successor field of the first node
(this was already discussed in terms of R-tuples in Section 3).

The goal of the algorithm is thus to reconstruct a journey by unfolding the
intervals and successor fields. Details are given in Algorithm 2.

Algorithm 2 reconstruct_journey(u, v, $t_{1}$, $t_{2}$)

1:$[t_{1},t_{2}]\subseteq{}\mathcal{T},u,v\in V,u\neq{}v$

2:$([t^{-},t^{+}],w)\leftarrow{}\textsc{find\mathunderscore{}next}(u,v,t_{1})$
$\triangleright$ node augmented with successor

3:if the return value is $nil$ or $t^{+}\leq t_{2}$ then

4: return $nil$ $\triangleright$ no interval contained in $[t_{1},t_{2}]$ in
$T(u,v)$

5:$\mathcal{J}\leftarrow{}\\{(u,w,t^{-})\\}$

6:while $w\neq v$ do

7:
$([t,\\_\,],w^{\prime})\leftarrow{}\textsc{find\mathunderscore{}next}(w,v,t^{-}+\delta)$

8: $\mathcal{J}\leftarrow{}\mathcal{J}\cdot\\{(w,w^{\prime},t)\\}$

9: $w\leftarrow{}w^{\prime}$

10: $t^{-}\leftarrow{}t$

11:return $\mathcal{J}$

The first step (Lines 1 to 3) is to retrieve a node in $T(u,v)$ whose interval
is contained within $[t_{1},t_{2}]$ if one exists. If several choices exist,
the earliest is selected (through calling the find_next primitive). Then, the
algorithm iteratively replaces $u$ with the successor and searches for the
next interval until the successor is $v$ itself (Lines 5 to 9), adding
gradually the corresponding contacts to a journey $\mathcal{J}$ (Line 4 and
Line 7), which is ultimately returned in Line 10.

######  Theorem 5.

Algorithm 2 has time complexity $O(k\log\tau)$, where $k$ is the length of the
resulting journey.

###### Proof.

The algorithm calls find_next in Line 1. After that, it is known whether a
journey can be reconstructed. If so, a journey prefix $\mathcal{J}$ is
initialized with the first contact of the reconstructed journey (indeed, such
a contact must exist due to the minimality of the interval). Then, in the loop
from Line 5 to Line 9, the algorithm extends $\mathcal{J}$ by one contact for
each call to find_next until $\mathcal{J}$ contains the entire journey.
Overall, find_next is thus called as many times as the length of the
reconstructed journey, which corresponds to $O(|\mathcal{J}|\log\tau)$ time.
The costs of the other operations are clearly dominated by this cost. ∎

####  4.3.1 Properties of the reconstructed journeys

In general, several journeys may exist that satisfy the query parameters. We
observe that the specific choices made in Algorithm 2 imply additional
properties.

######  Lemma 6.

The journey $\mathcal{J}$ which is returned by Algorithm 2 is a _foremost_
journey in the requested interval (i.e., it arrives at the earliest possible
time at $v$). Furthermore, among all the possible foremost journeys, it is
also a _fastest_ journey (i.e., the difference between departure time and
arrival time is minimized).

###### Proof.

The fact that $\mathcal{J}$ is a foremost journey follows from the call to
find_next in Line 1. Indeed, the interval returned by this call corresponds to
the earliest departure from $u$, which happens to also correspond to the
earliest arrival at $v$ because the stored intervals are incomparable.
$\mathcal{J}$ thus achieves the earliest possible arrival time at $v$ in the
given interval. And since all the stored intervals are _minimal_ (i.e. they do
not contain smaller reachability intervals), it also follows that
$departure(\mathcal{J})$ is as late as possible among all the journeys
arriving in $v$ at time $arrival(\mathcal{J})$, which means $\mathcal{J}$ is
as fast as possible among all foremost journeys. ∎

Let us insist that Lemma 6 does not imply that $\mathcal{J}$ is both foremost
and fastest in the requested interval. It only states that $\mathcal{J}$ is a
foremost journey, and a fastest one _among_ the possible foremost journeys.
Even faster journeys might exist in the requested interval, arriving later at
$v$. The above property is however already convenient, e.g. in communication
networks, where a message would arrive at destination as early as possible,
while (secondarily) traveling for as little time as possible.

##  5 Conclusion and open questions

We presented in this paper an incremental data structure to solve the dynamic
connectivity problem in temporal graphs. Our data structure places a high
priority on the query time, by answering reachability questions in time
$O(\log\tau)$. Based on the ability to retrieve reachability information for
particular time intervals, it supports the insertion of contacts in a non-
chronological order in $O(n^{2}\log\tau)$ amortized time (deterministic worst-
case $O(n^{2}\tau)$ time) and makes it possible to reconstruct efficiently
foremost journeys within a given time interval, i.e., in time $O(k\log\tau)$,
where $k$ is the size of the resulting journey. Our algorithms exploit the
special features of non-redundant (minimal) reachability information, which we
represent through the concept of R-tuples. The core of our data structure,
namely the _timed transitive closure_ (TTC), is itself essentially a
collection of irredundant R-tuples, whose size (and that of the data structure
itself) cannot exceed $O(n^{2}\tau)$.

The theory of R-tuples, initiated in this paper, poses a number of further
questions, some of which are of independent interest, some leading to possible
improvements of the presented algorithms. For example, do R-tuples involving
different pairs of vertices possess further interdependence which may reduce
the space needed to maintain TTCs? More generally, how restricted are TTCs
intrinsically? On the practical side, can we improve the insertion time for
new contacts by using another low-level structure than a balanced BST? Could
the notion of contacts be generalized to contacts of arbitrary duration?
Finally, designing efficient data structures for the decremental and the
fully-dynamic versions of this problem, with _unsorted_ contact insertion and
deletion, seems to represent both a significant challenge and a natural
extension of the present work, one that would certainly develop further our
common understanding of temporal reachability.

##### Acknowledgements

This study was financed in part by Fundação de Amparo à Pesquisa do Estado de
Minas Gerais (FAPEMIG) and the Coordenação de Aperfeiçoamento de Pessoal de
Nível Superior - Brasil (CAPES) - Finance Code 001* - under the “CAPES PrInt
program” awarded to the Computer Science Post-graduate Program of the Federal
University of Uberlândia, as well as the Agence Nationale de la Recherche
through ANR project ESTATE (ANR-16-CE25-0009-03).

## References

  * [1] R. Agrawal, A. Borgida and H.. Jagadish  “Efficient management of transitive relationships in large data and knowledge bases”  In _Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data_ , SIGMOD ’89  Portland, Oregon, USA: Association for Computing Machinery, 1989, pp. 253–262
  * [2] Matthieu Barjon et al.  “Testing temporal connectivity in sparse dynamic graphs”  In _CoRR_ abs/1404.7634, 2014
  * [3] L. Bedogni, M. Fiore and C. Glacet  “Temporal reachability in vehicular networks”  In _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications_ , 2018, pp. 81–89
  * [4] Daniel Bryce and Subbarao Kambhampati  “A tutorial on planning graph based reachability heuristics”  In _AI Magazine_ 28.1, 2007, pp. 47
  * [5] Leo Cacciari and Omar Rafiq  “A temporal reachability analysis”  In _Protocol Specification, Testing and Verification XV: Proceedings of the Fifteenth IFIP WG6.1 International Symposium on Protocol Specification, Testing and Verification, Warsaw, Poland, June 1995_ Boston, MA: Springer US, 1996, pp. 35–49
  * [6] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi and Nicola Santoro  “Time-varying graphs and dynamic networks”  In _International Journal of Parallel, Emergent and Distributed Systems_ 27.5 Taylor & Francis, 2012, pp. 387–408
  * [7] Edith Cohen, Eran Halperin, Haim Kaplan and Uri Zwick  “Reachability and distance queries via 2-hop labels”  In _SIAM Journal on Computing_ 32.5, 2003, pp. 1338–1355  DOI: 10.1137/S0097539702403098
  * [8] Jessica Enright, Kitty Meeks, George B. Mertzios and Viktor Zamaraev  “Deleting edges to restrict the size of an epidemic in temporal networks”, 2018
  * [9] Betsy George, Sangho Kim and Shashi Shekhar  “Spatio-temporal network databases and routing algorithms: a summary of results”  In _Advances in Spatial and Temporal Databases_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 460–477
  * [10] Haixun Wang et al.  “Dual labeling: answering graph reachability queries in constant time”  In _22nd International Conference on Data Engineering (ICDE’06)_ , 2006, pp. 75–75
  * [11] Khandaker Tabin Hasan, Sheak Rashed Haider Noori, Abdus SalamИ and Md Anwarul Kabir  “Making sense of time: timeline visualization for public transport schedule”  In _Symposium on Human-Computer Interaction and Information Retrieval (HCIR 2011), Washington_ , 2011
  * [12] C. Hurter et al.  “Bundled visualization of dynamicgraph and trail data”  In _IEEE Transactions on Visualization and Computer Graphics_ 20.8, 2014, pp. 1141–1157
  * [13] Matthieu Latapy, Tiphaine Viard and Clémence Magnien  “Stream graphs and link streams for the modeling of interactions over time”  In _Social Network Analysis and Mining_ 8.1 Springer, 2018, pp. 1–29
  * [14] Stefano Leucci  “Remove range of keys from Binary Search Tree in O(s+h)” URL:https://cs.stackexchange.com/q/123535 (version: 2020-04-02), Computer Science Stack Exchange  URL: https://cs.stackexchange.com/q/123535
  * [15] Alexandre Camargo Martensen, Santiago Saura and Marie-Josee Fortin  “Spatio-temporal connectivity: assessing the amount of reachable habitat in dynamic landscapes”  In _Methods in Ecology and Evolution_ 8.10, 2017, pp. 1253–1264
  * [16] Vera Zaychik Moffitt and Julia Stoyanovich  “Querying evolving graphs with portal”, 2016
  * [17] Polina Rozenshtein, Aristides Gionis, B. Prakash and Jilles Vreeken  “Reconstructing an epidemic over time”  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16  San Francisco, California, USA: Association for Computing Machinery, 2016, pp. 1835–1844
  * [18] S. Seufert, A. Anand, S. Bedathur and G. Weikum  “FERRARI: flexible and efficient reachability range assignment for graph indexing”  In _2013 IEEE 29th International Conference on Data Engineering (ICDE)_ , 2013, pp. 1009–1020
  * [19] John Tang, Mirco Musolesi, Cecilia Mascolo and Vito Latora  “Characterising temporal distance and reachability in mobile and online social networks”  In _SIGCOMM Comput. Commun. Rev._ 40.1 New York, NY, USA: Association for Computing Machinery, 2010, pp. 118–124
  * [20] Hao Wei, Jeffrey Xu Yu, Can Lu and Ruoming Jin  “Reachability querying: an independent permutation labeling approach”  In _The VLDB Journal_ 27.1 Springer, 2018, pp. 1–26
  * [21] John Whitbeck, Marcelo Dias de Amorim, Vania Conan and Jean-Loup Guillaume  “Temporal reachability graphs”  In _Proceedings of the 18th Annual International Conference on Mobile Computing and Networking_ , Mobicom ’12  Istanbul, Turkey: Association for Computing Machinery, 2012, pp. 377–388
  * [22] Matthew J. Williams and Mirco Musolesi  “Spatio-temporal networks: reachability, centrality and robustness”  In _Royal Society Open Science_ 3.6, 2016, pp. 160196
  * [23] G. Wu et al.  “Mining spatio-temporal reachable regions over massive trajectory data”  In _2017 IEEE 33rd International Conference on Data Engineering (ICDE)_ , 2017, pp. 1283–1294
  * [24] H. Wu et al.  “Reachability and time-based path queries in temporal graphs”  In _2016 IEEE 32nd International Conference on Data Engineering (ICDE)_ , 2016, pp. 145–156
  * [25] H. Xiao, C. Aslay and A. Gionis  “Robust cascade reconstruction by steiner tree sampling”  In _2018 IEEE International Conference on Data Mining (ICDM)_ , 2018, pp. 637–646
  * [26] Han Xiao, Polina Rozenshtein, Nikolaj Tatti and Aristides Gionis  “Reconstructing a cascade from temporal observations”  In _Proceedings of the 2018 SIAM International Conference on Data Mining_ , pp. 666–674
  * [27] B. Xuan, A. Ferreira and A. Jarry  “Computing shortest, fastest, and foremost journeys in dynamic networks”  In _International Journal of Foundations of Computer Science_ 14.02, 2003, pp. 267–285
  * [28] W. Zeng et al.  “Visualizing mobility of public transportation system”  In _IEEE Transactions on Visualization and Computer Graphics_ 20.12, 2014, pp. 1833–1842
  * [29] Andy Diwen Zhu, Wenqing Lin, Sibo Wang and Xiaokui Xiao  “Reachability queries on large dynamic graphs: a total order approach”  In _Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data_ , SIGMOD ’14  Snowbird, Utah, USA: Association for Computing Machinery, 2014, pp. 1323–1334