Temporal cliques admit sparse spanners

DOI10.1016/j.jcss.2021.04.004OpenAlexW3157160562MaRDI QIDQ2040022

Jason Schoeters, Joseph G. Peters, Arnaud Casteigts

Publication date: 6 July 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.00104

zbMATH Keywords

reachabilitygraph spannersdynamic networkstemporal graphstemporal connectivitypivotabilitydismountability

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (7)

Blackout-tolerant temporal spanners ⋮ Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Blackout-tolerant temporal spanners ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Finding temporal paths under waiting time constraints ⋮ Feedback edge sets in temporal graphs

Uses Software

• cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing maximal cliques in link streams
• Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
• Distributed exploration of dynamic rings
• The complexity of optimal design of temporally connected graphs
• On temporal graph exploration
• 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
• Temporal Cliques Admit Sparse Spanners
• Temporal Network Theory
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Computing maximum matchings in temporal graphs.
• Connectivity and inference problems for temporal networks
• Temporal graph classes: a view through temporal separators

This page was built for publication: Temporal cliques admit sparse spanners