Sparse temporal spanners with low stretch

DOI10.4230/LIPICS.ESA.2022.19MaRDI QIDQ6969668zbMATH OpenFDO

Authors D. Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, Mirko Rossi

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.19

zbMATH Keywords

approximate distancesgraph sparsificationtemporal graphstemporal spanners

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Connectivity and inference problems for temporal networks
• Graph spanners: a tutorial review
• Improved purely additive fault-tolerant spanners
• On sparse spanners of weighted graphs
• On the size and the approximability of minimum temporally connected subgraphs
• Sharp thresholds in random simple temporal graphs
• Temporal cliques admit sparse spanners
• Temporal network optimization subject to connectivity constraints
• The complexity of optimal design of temporally connected graphs

Cited in

(5)

• How to reduce temporal cliques to find sparse spanners
• Temporal queries for dynamic temporal forests
• Temporal graph realization with bounded stretch
• Canadian traveler problems in temporal graphs
• Temporal graph realization with bounded stretch

This page was built for publication: Sparse temporal spanners with low stretch

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969668)