  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.
