Abstract: A temporal graph is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence G1,G2…,Gl of static graphs over the same (static) set of nodes V. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension in added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporalgraphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporalgraphs and temporal graph problems that have appeared in the Computer Science community.
Abstract: In this work we consider temporalgraphs, i.e. graphs, each edge of which isassigned a set of discrete time-labels drawn from a set of integers. The labelsof an edge indicate the discrete moments in time at which the edge isavailable. We also consider temporal paths in a temporal graph, i.e. pathswhose edges are assigned a strictly increasing sequence of labels. Furthermore,we assume the uniform case (UNI-CASE), in which every edge of a graph isassigned exactly one time label from a set of integers and the time labelsassigned to the edges of the graph are chosen randomly and independently, withthe selection following the uniform distribution. We call uniform randomtemporalgraphs the graphs that satisfy the UNI-CASE. We begin by deriving theexpected number of temporal paths of a given length in the uniform randomtemporal clique. We define the term temporal distance of two vertices, which isthe arrival time, i.e. the time-label of the last edge, of the temporal paththat connects those vertices, which has the smallest arrival time amongst alltemporal paths that connect those vertices. We then propose and study twostatistical properties of temporalgraphs. One is the maximum expected temporaldistance which is, as the term indicates, the maximum of all expected temporaldistances in the graph. The other one is the temporal diameter which, looselyspeaking, is the expectation of the maximum temporal distance in the graph. Wederive the maximum expected temporal distance of a uniform random temporal stargraph as well as an upper bound on both the maximum expected temporal distanceand the temporal diameter of the normalized version of the uniform randomtemporal clique, in which the largest time-label available equals the number ofvertices. Finally, we provide an algorithm that solves an optimization problemon a specific type of temporal (multi)graphs of two vertices.
Abstract: In this work we consider temporal networks, i.e. networks defined by a labeling $\lambda$ assigning to each edge of an underlying graph G a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular, we consider time-respecting paths, i.e. paths whose edges are assigned by $\lambda$ a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally, we propose two cost minimization parameters for temporal network design. One is the temporality of G, in which the goal is to minimize the maximum number of labels of an edge, and the other is the temporal cost of G, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some connectivity constraint. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.
Abstract: In this work, we introduce the notion of time to some well-known combinatorial optimization problems. In particular, we study problems defined on temporalgraphs. A temporal graph D=(V,A) may be viewed as a time-sequence G_1,G_2,...,G_l of static graphs over the same (static) set of nodes V. Each G_t = D(t) = (V,A(t)) is called the instance of D at time t and l is called the lifetime of D. Our main focus is on analogues of traveling salesman problems in temporalgraphs. A sequence of time-labeled edges (e.g. a tour) is called temporal if its labels are strictly increasing. We begin by considering the problem of exploring the nodes of a temporal graph as soon as possible. In contrast to the positive results known for the static case, we prove that, it cannot be approximated within cn, for some constant c > 0, in general temporalgraphs and within (2 − \varepsilon), for every constant \varepsilon > 0, in the special case in which D(t) is connected for all 1 <= t <= l, both unless P = NP. We then study the temporal analogue of TSP(1,2), abbreviated TTSP(1,2), where, for all 1 <= t <= l, D(t) is a complete weighted graph with edge-costs from {1,2} and the cost of an edge may vary from instance to instance. The goal is to find a minimum cost temporal TSP tour. We give several polynomial-time approximation algorithms for TTSP(1,2). Our best approximation is (1.7 + \varepsilon) for the generic TTSP(1,2) and (13/8 + \varepsilon) for its interesting special case in which the lifetime of the temporal graph is restricted to n. In the way, we also introduce temporal versions of Maximum Matching, Path Packing, Max-TSP, and Minimum Cycle Cover, for which we obtain polynomial-time approximation algorithms and hardness results.
