Networks Workshop - Jason Schoeters (Cambridge)

Title: On Inefficiently Connecting Temporal Networks, with Esteban Christiann and Eric Sanlaville

Abstract:
Temporal network design studies how to optimally design networks with connections over time, modelled as a temporal graph, which are often represented as a graph with an edge labelling. This area of research has previously focused on minimising the number of labels to ensure temporal connectivity, whether optimising the total or local number of labels, all-to-all or terminal-to-terminal connectivity, or with additional constraints such as limiting the age of the network. In this work, we focus on trying to achieve the maximum number of connections, such that all such connections are necessary for reachability. This can represent the power of an adversary trying to waste temporal network resources, even when constrained. This also implies worst-case results for temporal spanner problems, or for corresponding greedy algorithms for finding such spanners. Our contributions are multiple: we present denser labellings than previous work; the first dense labellings maximizing a novel measure; structural results for basic graph families, which are then extended to larger graph families; and an extension of an efficient temporal graph labelling generator. Over the course of the paper, we make some bounds meet exactly or asymptotically, and leave some interesting open questions in the conclusion.