# Foremost Walks and Paths in Interval Temporal Graphs +
## 1 Introduction  
Temporal graphs are graphs in which the edges connecting vertices or the characteristics of these edges may change with time. The applications of temporal graphs include the spread of viral diseases, information dissemination by means of physical/virtual contact between people, understanding behavior in online social networks, modeling data transmission in phone networks, modeling traffic flow in road networks, and studying biological networks at the molecular level [1; 2; 3; 4; 5; 6; 7]. Two popular categories of temporal or dynamic graphs are contact-sequence (temporal) graphs and interval-temporal graphs. In a contact-sequence graph, each directed edge \((u,v)\) has the label \((departure\_time,travel\_duration)\), where \(departure\_time\) is the time at which one can leave vertex \(u\) along edge \((u,v)\) and \(travel\_duration\) is the time it takes to traverse the edge. Therefore, vertex \(v\) is reached at time \(departure\_time+travel\_time\). Note that a contact-sequence graph may have many edges from vertex \(u\) to vertex \(v\); each edge has a different \(departure\_time\). In an interval-temporal graph, each directed edge \((u,v)\) has a label that is comprised of one or more tuples of the form \((start\_time,end\_time,travel\_duration)\), where \(start\_time\leq end\_time\) defines an interval of times at which one can depart vertex \(u\). If one departs \(u\) at time \(t\), \(start\_time\leq t\leq end\_time\), one reaches \(v\) at time \(t+travel\_duration\). The intervals associated with the possibly many tuples that comprise the label of an edge \((u,v)\) must be disjoint. Figures 1 and 2 are examples of contact-sequence and interval-temporal graphs, respectively. A (time-respecting) _walk_ in a temporal graph is a sequence of edges with the property that the end vertex of one edge is the start vertex of the next edge (if any) on the walk, each edge is labeled by the departure time from the start vertex of the edge, and the departure time label on each edge is a valid departure time for that edge and is greater than or equal to the arrival time (if any) at the edge's start vertex (A more formal definition is provided inSection 2). A (time-respecting) \(path\) is a walk in which no vertex is repeated (i.e., there is no cycle). \(<S,1,A,2,B>\) and \(<S,0,B,5,C>\) are example walks in the temporal graphs of Figures 1 and 2, respectively. Both walks are also paths. An application that can be modeled with a contact-sequence graph is a flight network. Each flight has a departure time at which it leaves the originating airport and a certain travel duration before it can reach the destination airport. On the other hand, if we consider the example of a road network, there is no single instance of time when one needs to depart on a given street. There may be different time windows (or time intervals) during which a street may be open for travel. Further, we may define time windows based on travel duration needed to reach from point \(A\) to point \(B\) on a given street due to different traffic  
Figure 1: Contact-sequence temporal graph. Figure 2: Interval-temporal graph. conditions during different times of the day (such as office hours). Such networks cannot be modeled using contact-sequence graphs, as a given time window represents infinitely many possible departure times and, hence, infinitely many contact sequence edges. It is easy to see that every contact-sequence graph can be modeled as an interval-temporal graph. Further, when time can be discretized, every interval-temporal graph can be modeled as a contact-sequence graph (with potentially an explosion in the number of edges). The authors of [8; 9; 10; 11] focus on finding optimal paths and walks. Optimization criteria such as \(foremost\) (arrive at the destination at the earliest possible time), \(minhop\) (use the fewest number of hops when going from the source to the destination vertex), \(shortest\) (the time taken to go from the source to the destination is minimized), and so on, are considered. [PERSON] et al.