Temporal Cliques Admit Sparse Spanners

DOI10.4230/LIPIcs.ICALP.2019.134OpenAlexW2964720952MaRDI QIDQ5092337

Jason Schoeters, Joseph G. Peters, Arnaud Casteigts

Publication date: 21 July 2022

Full work available at URL: https://hal.science/hal-02380356

zbMATH Keywords

dynamic networkstemporal graphstemporal connectivitysparse spanners

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (4)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Maximum 0-1 timed matching on temporal graphs ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Temporal cliques admit sparse spanners

Cites Work

• Unnamed Item
• Computing maximal cliques in link streams
• Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
• The complexity of optimal design of temporally connected graphs
• Geometric Spanner Networks
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Graph spanners
• On the Size and the Approximability of Minimum Temporally Connected Subgraphs
• The Complexity of Finding Small Separators in Temporal Graphs
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• Connectivity and inference problems for temporal networks

This page was built for publication: Temporal Cliques Admit Sparse Spanners