In this work we consider \emph{temporal networks}, i.e.~networks defined by a \emph{labeling} $\lambda$ assigning to each edge of an \emph{underlying graph} $G$ a set of \emph{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 \emph{path problems} of temporal networks. In particular, we consider \emph{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 \emph{natural analogue of Menger's theorem} holding for arbitrary temporal networks. Finally, we propose two \emph{cost minimization parameters} for temporal network design. One is the \emph{temporality} of $G$, in which the goal is to minimize the maximum number of labels of an edge, and the other is the \emph{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 \emph{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.
@article{MMS18,
author = {Mertzios, George B and Michail, Othon and Spirakis, Paul G},
title = {Temporal Network Optimization Subject to Connectivity Constraints},
journal = {Algorithmica},
volume = {},
number = {},
pages = {1--34},
year = {2018},
issn = {0178-4617},
doi = {http://dx.doi.org/10.1007/s00453-018-0478-6},
url = {http://link.springer.com/article/10.1007/s00453-018-0478-6},
publisher = {Springer Nature}
}
@inproceedings{MMCS13,
title={Temporal Network Optimization Subject to Connectivity Constraints},
author={Mertzios, George B and Michail, Othon and Chatzigiannakis, Ioannis and Spirakis, Paul G},
booktitle={40th International Colloquium on Automata, Languages and Programming (ICALP)},
pages={663--674},
year={2013},
volume={7966},
number={Part 2},
series={Lecture Notes in Computer Science},
month={July},
publisher={Springer}
}