# Path Algorithms for Contact Sequence Temporal Graphs +
## 1 Introduction
Examples of the different types of time-respecting paths used in the literature can be found in [7; 8]. The input of a typical path-finding problem is an interval \([t_{start},t_{end}]\). Here, \(t_{start}\) is the earliest time we can start from the source and \(t_{end}\) is the latest time we are allowed to arrive at the destination. Let \(u\) be the source and \(v\) the destination vertices, respectively. The _feasible paths_ from \(u\) to \(v\) are defined as time-respecting paths that leave \(u\) at or after \(t_{start}\) and arrive at \(v\) at or before \(t_{end}\). The paths we study in this paper should all be feasible. The earliest arrival or foremost path minimizes the arrival time at \(v\). The fastest path minimizes the difference between the arrival time at \(v\) and the departure time from \(u\). A shortest path minimizes the sum of the weights of the edges on the path, and a min-hop path minimizes the number of edges on the path. A _Time Respecting Graph (TRG)_ is a graph in which all the paths are time respecting. [PERSON] et al. [8] propose two models to represent contact sequence temporal graphs. The first is a time-ordered sequence of edges (i.e., non-decreasing order of timestamps), which we call OSE in this paper, and the second is a model based on the time-respecting nature of the graph, which we call TRG_Wu. They develop algorithms for finding single-source, all-destinations optimal paths for both models. Their proposed algorithms based on the contact sequence temporal graph modeling are more efficient than those proposed in [7], which are based on the interval temporal graph models. Moreover, they show that their OSE algorithms are faster than their TRG_Wu algorithms for all considered path-finding problems, except for the fastest paths problem, where each model was faster on some datasets and slower on others. Although it has been shown that the OSE-based algorithms are faster than those based on the TRG_Wu model for a specific group of path-finding problems, they are certainly slower on other problems. One group of those problems depends on the local properties of the graph. An example is the problem of finding the existence of a one-hop or two-hop path between two vertices. Therefore, developing a model superior to TRG_Wu on shallow-neighborhood-search problems and competitive with or more efficient than OSE on single-source all-destinations path-finding problems is very beneficial. We note that the OSE algorithms of [PERSON] et al. [8] require that all edges of the temporal contact sequence graph have a strictly positive weight. [PERSON] et al. [9] propose an alternative TRG data structure, TRG_Zhoche, for contact sequence temporal graphs. This data structure requires all edge weights to be integer and \(>\)0. They develop a linear-time algorithm based on the topological ordering of vertices for the single-source all-destinations shortest paths problem. In this paper, we propose a new model for TRGs that we call TRG_Ours. Our proposed model is more memory-efficient than both TRG_Wu and TRG_Zschoche. We develop algorithms for the single-source all-destinations fastest, minhop, shortest and foremost path problems and use them to show the effectiveness of our model relative to TRG_Wu. We also propose algorithms for the case when the TRG graphs are acyclic and demonstrate the effectiveness of our algorithms using the same path problems. The outline of this paper is as follows. Related work is reviewed in Section 1. The TRG models TRG_Wu, TRG_Zschoche, and TRG_Ours are described in Section 2.1, and the memory requirements of each are analyzed. Our algorithms for general TRG_Ours are described in Section 2.2, and our algorithms for acyclic TRG_Ours are described in Section 2.3. Experimental results are presented in Section 3.1. We conclude in Section 4. Related WorkWe have already mentioned the models proposed by [PERSON] et al. [8] in Section 1. Due to the closeness of their work to ours, we will discuss their method in detail in the following sections.