Almost Linear 3-Spanners of Temporal Cliques
A simple recursive algorithm is presented that computes, for every temporal clique on $n$ vertices, a temporal $3-spanner of size $n^{1+2/\sqrt{\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\widetilde{\mathcal{O}}(n^{3/2})$.
Júlia Baligács, Davide Bilò, Václav Blažej et al.
· 0 citations