{"id":"arxiv/2609.02851","url":"https://arxiv.org/abs/2609.02851","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Almost Linear 3-Spanners of Temporal Cliques","domain":"cs.DS","source":"arxiv","authors":["Julia Baligacs","Davide Bilò","Václav Blažej","Maël Dumas","Anna Zych-Pawlewicz"],"reviews":0,"subject":"cs.DS","summary":"Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal $α$-spanner of a temporal graph with $n$ vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of $α$. While general temporal graphs may not admit sparse temporal $α$-spanners for any value of $α$, temporal cliques are known to admit temporal $(2k-1)$-spanners of size $\\widetilde{\\mathcal{O}}(kn^{1+1/k})$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}