# Path Algorithms for Contact Sequence Temporal Graphs +
## 1 Introduction
Their work improves on the work of [PERSON] et al. [7] for interval temporal graphs. Finding optimal paths in the presence of constraints is the focus of another group of methods. Examples are the works of [10; 11] for finding approximate optimal paths. In the problems studied by [PERSON] et al. [12], edge labels are used for classification purposes. Examples of edge labels are family /friend relationships in social networks. [PERSON] et al. [13] propose a model that allows adding min and max wait times to each vertex. Their proposed model can be used to optimize a linear combination of criteria (e.g., fastest, shortest, foremost). They show the median runtime of their algorithm to be comparable with those proposed in [8]. However, the average runtime of their algorithm is around 10 times greater than those used in [8] (the average is taken over all the optimization criteria). The work by [PERSON] et al. [14] is an extension of this work which considers more optimization criteria, provides the missing proofs, and presents extended experimental results. [PERSON] et al. [15] use a TRG similar to that of [9] with the main difference that they connect an edge to a node only if the timestamp of the edge is within \(\delta\) of the timestamp of the node (where \(\delta\) is an upper bound on the time one could remain in a node). When the edge updates are not known in advance, another group of methods can be used, such as the ones in [16; 17; 18]. They form Shortest Path Trees (SPTs) rooted at each vertex. The trees are updated after each temporal evolution of the graph. Some methods choose a group of vertices as the landmark nodes. They then run a pre-processing step to calculate the distances from each vertex to those landmark nodes. These partial distances are combined to calculate the distances between each pair of vertices and are updated each time the graph evolves. Different types of landmark nodes have been considered in the literature. Examples are the hub nodes [19], nodes in a radius of \(K\) from a given node [20] and nodes for which the triangle equality holds for a sample subset of paths [21]. These methods are appropriate for problems in which edge updates are not known in advance. [PERSON] et al. [22] show that TRG_Wu is acyclic for contact sequence temporal graphs with no edge weight equal to 0. They develop an indexing scheme to efficiently answer reachability and time-based fastest and shortest paths queries for acyclic TRG_Wu. They allow for the contact sequence graph and hence its TRG_Wu to change over time by adding edges. The algorithms developed by [PERSON] [23] also benefit from the topological ordering of nodes in the acyclic transformation of dynamic graphs. Their transformed graph is divided into different temporal snapshots. The minimum cost paths algorithm uses dynamic programming on the topologically sorted vertices in reverse chronological order. A graph model has been used in [24] in which the geographic locations of the nodes determine their distances, and the nodes can be added or removed dynamically with time. The temporal evolution of the vertices has also been studied in other work such as [25]. We may need to calculate the upper bounds on the length of the optimal paths. An example application is the mobile ad-hoc networks in which flooding time can be used to compute the upper bound on the length of the fastest path. The search space for finding a semi-optimal path can be reduced by putting an upper bound of the flooding time [26]. Differential equations have been used in self-adapting methods that converge to the optimal paths for a fixed source node and edge updates that are not known in advance [27]. Path algorithms largely depend on the specific problem requirements. Different models and algorithms have been developed, each with emphasis on a particular requirement such as query response time [28], security [29], path difference between two consecutive graph snapshots [30] and number of destination nodes [31]. [PERSON] et al.