Almost Linear 3-Spanners of Temporal Cliques

Source: arxiv.org/abs/2609.02851

Julia Baligacs, Davide Bilò, Václav Blažej, Maël Dumas, Anna Zych-Pawlewicz

arXivarxiv/2609.02851Sep 2, 2026cs.DSscore 0

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})$…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.02851
curl -X POST /api/v1/records/arxiv/2609.02851/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.02851/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'