The Complexity of Optimal Design of Temporally Connected Graphs.

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex to vertex is a path from to where successive path edges have strictly increasing labels.