Metraipolis › archive › dc_dda23990acec
Almost Linear 3-Spanners of Temporal Cliques — arXiv:2609.02851
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.02851
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T05:41:27.795Z
- SHA-256 of the archived text
282f421b9dc099395a665e7fd37ffcb27bccc6f225f949171ec69fc10f6ff027- Stable URL of this page
https://metraipolis.com/documento/dc_dda23990acec
How to cite
Almost Linear 3-Spanners of Temporal Cliques — arXiv:2609.02851 — arXiv (en), https://arxiv.org/abs/2609.02851 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dda23990acec (Metraipolis archive dc_dda23990acec, sha256 282f421b9dc099395a665e7fd37ffcb27bccc6f225f949171ec69fc10f6ff027)
BibTeX
@misc{dcdda23990acec,
title = {Almost Linear 3-Spanners of Temporal Cliques — arXiv:2609.02851},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.02851},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dda23990acec; sha256 282f421b9dc099395a665e7fd37ffcb27bccc6f225f949171ec69fc10f6ff027},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02851. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\alpha$-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 $\alpha$. While general temporal graphs may not admit sparse temporal $\alpha$-spanners for any value of $\alpha$, temporal cliques are known to admit temporal $(2k-1)$-spanners of size $\widetilde{\mathcal{O}}(kn^{1+1/k})$ for every positive integer $k$. We present a simple recursive algorithm 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})$. We also show that a modified version of our algorithm computes temporal $3$-spanners of size $\mathcal{O}(nL)$ when the lifetime is bounded by $L$, i.e., all time labels are in $\{1,\ldots,L\}$, thus improving the previous bound of $\mathcal{O}(2^Ln\log n)$. Both results are particularly striking in light of the known lower bound of $\Omega(n^2)$ on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime $L\geq 3$. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only $\mathcal{O}(n)$ carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-03 in math.CO).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.02851 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T04:59:51.806Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).