Temporal Cliques Admit Sparse Spanners

Arnaud Casteigts, Joseph G. Peters, Jason Schoeters

Let $G=(V,E)$ be an undirected graph on $n$ vertices and $\lambda :E\to 2^{\mathbb{N}}$ a mapping that assigns to every edge a non-empty set of integer labels (times). Such a graph is {\e…